Codeforces #319 Div1 C. Points on Plane

またしょうもないミスで損した。
http://codeforces.com/contest/576/problem/C

問題

２次元座標上で、(0,0)-(10^6,10^6)の範囲でN個(N≦10^6)の異なる格子点が与えられる。
これらの点を任意の点で開始し、全頂点を最低１回ずつ通るルートを作りたい。
２点間の距離がマンハッタン距離で計算されるとき、ルートの総長が2.5*10^9以下のものを答えよ。

解法

平面を大まかに区切って、その範囲でソートするようにすると良い。
例えばX座標をPごとに区切り、左端の列を上から下まで走査したあと、右隣の列を下から上、また右の列を上から下まで…と蛇腹状にたどる。
こうすると、縦の移動量は、列の数が10^6/Pなので10^12/Pとなる。
また横の移動量は、列を跨ぐとき以外はP以下なので合計N*P回、列を跨ぐのは最大10^6/P回、１回列を跨ぐの移動量は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を決めるところで若干考察が必要だね。