Codeforces #331 Div2 C. Wilbur and Points

ABCDサクサク解けたと思ったらCもDも落とした。
http://codeforces.com/contest/596/problem/C

問題

2次元座標において、x,y座標が非負の格子点がN個与えられる。
点(x,y)がある集合に属す場合、0≦x'≦xかつ0≦y'≦yである(x',y')もその集合に属すとする。
与えられる格子点の集合は、上記条件を満たしている。

このN個に1～Nの番号を、以下の条件を満たしつつ振りたい。

• (x,y)に番号aを振ったとき、対応する点(x',y')の番号は全てa以下である。
• 数列W[a]が与えられる。番号aを振るのはy-x=W[a]を満たす点でなければならない。

条件を満たす振り方は存在するか。
するな振り方を答えよ。

解法

1から順に数値aを振る点を求めていこう。
y-x=W[a]を満たす格子点は左下から右上に伸びる直線状に配置される。
問題文の条件より、そのy-x=W[a]上にある番号未割当の点で最も左下にある点を貪欲に取っていこう。

その際、対応する(x',y')に点があるとアウトである。
問題文の条件より、初期状態では(x',y')がすべて詰まっているはずなので、(x-1,y)及び(x,y-1)に未割当の点が残っているかチェックだけすればいい。
(x-1,y)と(x,y-1)が割り当て済みなら、(x',y')はすべて割り当て済みになるはずである。

int N;
int X[101010],Y[101010];

int W[101010];
int ret[202020],px[202020];
map<pair<int,int>,int> pt;

void solve() {
	int i,j,k,l,r,x,y,w; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		pt[{X[i],Y[i]}]=i;
	}
	for(i=-100000;i<0;i++) px[101010+i]=-i;
	FOR(i,N) {
		cin>>w;
		int wp=w+101010;
		if(pt.count({px[wp],w+px[wp]})==0) return _P("NO\n");
		ret[i]=r=pt[{px[wp],w+px[wp]}];
		pt.erase({X[r],Y[r]});
		px[wp]++;
		if(pt.count({X[r]-1,Y[r]}) || pt.count({X[r],Y[r]-1})) return _P("NO\n");
	}
	
	_P("YES\n");
	FOR(i,N) _P("%d %d\n",X[ret[i]],Y[ret[i]]);
	
}

まとめ

本番何を勘違いしたか、y-x=W[a]を満たす格子点は左上から右下に伸びる直線状にあると考えてしまい誤回答。