Codeforces #1018 : D. Wonderful Lightbulbs

ちょっと微妙な出来だった回。
https://codeforces.com/contest/2096/problem/D

問題

2次元座標の格子点上に電球がある。
初期状態である1点のみ電球が点いている。

その後、点(x,y)を指定し、(x,y)(x+1,y)(x+1,y-1)(x+1,y)の4点の電球のオンオフを反転させる、ということを繰り返した。
最終的な電球の状態が与えられるとき、最初につけた電球の位置を特定せよ。

解法

y'=x+yと座標変換すると、オンオフする電球は(x,y')の指定に対し(x,y')(x+1,y')(x,y'+1)(x+1,y'+1)の4点となる。
よって、このオンオフの作業は各x,y'の座標におけるオンオフの電球の数が2個ずつ切り替わる。

そのため、電球が1個しかないx,y'が解となる。

int T,N;
ll X[202020],Y[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> Xs,Ys;
		FOR(i,N) {
			cin>>X[i]>>Y[i];
			Y[i]+=X[i];
			if(Xs.count(X[i])) {
				Xs.erase(X[i]);
			}
			else {
				Xs.insert(X[i]);
			}
			if(Ys.count(Y[i])) {
				Ys.erase(Y[i]);
			}
			else {
				Ys.insert(Y[i]);
			}
		}
		assert(Xs.size()==1);
		assert(Ys.size()==1);
		x=*Xs.begin();
		y=*Ys.begin()-x;
		cout<<x<<" "<<y<<endl;
		
	}
		
}

まとめ

嵌るとなかなか解けなさそう。
本番そこそこの時間で思いつけて良かった。