またしょうもないミスで損した。
http://codeforces.com/contest/576/problem/C
問題
2次元座標上で、(0,0)-(10^6,10^6)の範囲でN個(N≦10^6)の異なる格子点が与えられる。
これらの点を任意の点で開始し、全頂点を最低1回ずつ通るルートを作りたい。
2点間の距離がマンハッタン距離で計算されるとき、ルートの総長が2.5*10^9以下のものを答えよ。
解法
平面を大まかに区切って、その範囲でソートするようにすると良い。
例えばX座標をPごとに区切り、左端の列を上から下まで走査したあと、右隣の列を下から上、また右の列を上から下まで…と蛇腹状にたどる。
こうすると、縦の移動量は、列の数が10^6/Pなので10^12/Pとなる。
また横の移動量は、列を跨ぐとき以外はP以下なので合計N*P回、列を跨ぐのは最大10^6/P回、1回列を跨ぐの移動量は2P以下なので2*10^6以下。
列を跨ぐケースは合計2*10^6で2.5*10^9よりずっと小さいので無視できる。
N上限が10^6であることを考えると、10^12/P + 10^6*P ≦ 2.5*10^9でなければならないので、P=10^3を取ると良い。
int N; pair<pair<int,int>,int> P[1010101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x>>y; P[i]={{x/1000,((x/1000)%2?-1:1)*y},i}; } sort(P,P+N); FOR(i,N) _P("%d%c",P[i].second+1,(i==N-1)?'\n':' '); }
まとめ
考え方もコードも単純だけど、Pを決めるところで若干考察が必要だね。