naoya_t@topcoder

SRM399 Div1 Easy: AvoidingProduct

過去問, 練習 | 18:04 |

走査範囲が狭くてシステムテスト落ち。書き直しの刑。（書き直しなのに6分17秒もかかったorz）

class AvoidingProduct {
public:
  vector<int> getTriple(vector<int> a, int n) {
    int dmin = 1000;
    int uplim = 2000+a[0]+1; //2000あれば大丈夫っぽい
    
    set<int> s; tr(a,it) s.insert(*it); // NGリスト

    int amin=1001;
    for(int i=1;i<=1000;i++) {
      if (s.find(i)==s.end()) {amin=i;break;}
    }
    int am3=amin*amin*amin;
    if (am3>n) { vector<int> ans(3,amin); return ans; }

    vector<int> ans(3,-1);

    for(int x=1;x<=uplim;x++){
      if (s.find(x)!=s.end()) continue;
      for(int y=x;y<=uplim;y++){
        if (s.find(y)!=s.end()) continue;
        int xy = x*y;
        if(xy>uplim) break;
        for(int z=y;z<=uplim;z++){
          if (s.find(z)!=s.end()) continue;
          int xyz = xy * z;
          if(xyz>uplim) break;
          int d = abs(n-xyz);
          if (d<dmin) {
            dmin = d;
            ans[0]=x; ans[1]=y; ans[2]=z;
          }
        }
      }
    }
    return ans;
  }
};