Codeforces #551 Div2 E. Serval and Snake

Eで苦戦しすぎてFに考えが至らず。
http://codeforces.com/contest/1153/problem/E

問題

　
N*Nのグリッド上にヘビがいるものとする。
ヘビはいくつかの隣接マスを順にたどった形状をしており、同じマスを2回通ることはない。
以下のクエリを2019回まで用いて、先頭と末尾の位置を求めよ。

クエリではグリッド上の矩形領域を指定すると、矩形領域の境界を横断する回数が返る。

解法

先頭と末尾のいずれか片方が矩形領域内にあると、横断回数が奇数回になる。
これを用いて処理して移行。

1行ずつクエリを指定していくと、横断回数が奇数回になる場合が0回または2回ある。
同様に1列ずつクエリを指定していくと、横断回数が奇数回になる場合が0回または2回ある。

少なくとも行と列いずれかは横断回数が奇数回になる箇所が2回ある。
そのような行または列に対し、さらに二分探索で列・行を特定していけばよい。

int N;
int R[1010],C[1010];

int ask(int x1,int y1,int x2,int y2) {
	int r;
	cout<<"? "<<(x1+1)<<" "<<(y1+1)<<" "<<(x2)<<" "<<(y2)<<endl;
	cin>>r;
	return r;
}

pair<int,int> getR(int y,int RS) {
	int LL=0,RR=N;
	RS%=2;
	while(RR-LL>1) {
		int MM=(LL+RR)/2;
		int n1=ask(LL,y,MM,y+1);
		int n2=n1^RS;
		
		if(n1%2) {
			RR=MM;
			RS=n1;
		}
		else {
			LL=MM;
			RS=n2;
		}
	}
	return {LL,y};
}

pair<int,int> getC(int x,int CS) {
	CS%=2;
	int LL=0,RR=N;
	while(RR-LL>1) {
		int MM=(LL+RR)/2;
		int n1=ask(x,LL,x+1,MM)%2;
		int n2=n1^CS;
		
		if(n1%2) {
			RR=MM;
			CS=n1;
		}
		else {
			LL=MM;
			CS=n2;
		}
	}
	return {x,LL};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> Rs,Cs;
	FOR(y,N-1) R[y+1]=ask(0,y,N,y+1)-R[y];
	FOR(x,N-1) C[x+1]=ask(x,0,x+1,N)-C[x];
	
	FOR(y,N) if((R[y]+R[y+1])%2) Rs.push_back(y);
	FOR(x,N) if((C[x]+C[x+1])%2) Cs.push_back(x);
	
	vector<pair<int,int>> P;
	
	
	if(Rs.size()==2) {
		P.push_back(getR(Rs[0],R[Rs[0]]+R[Rs[0]+1]));
		P.push_back(getR(Rs[1],R[Rs[1]]+R[Rs[1]+1]));
	}
	else {
		P.push_back(getC(Cs[0],C[Cs[0]]+C[Cs[0]+1]));
		P.push_back(getC(Cs[1],C[Cs[1]]+C[Cs[1]+1]));
	}
	
	cout<<"! "<<P[0].first+1<<" "<<P[0].second+1<<" "<<P[1].first+1<<" "<<P[1].second+1<<endl;
}

まとめ

Dまでの難易度に対し、E,Fが妙に難しかった回。