yukicoder : No.3161 Find Presents

これは割と簡単な気がする。
https://yukicoder.me/problems/no/3161

問題

2次元座標上でN個の格子点の位置を特定するinteractive問題である。
矩形領域を指定すると、その中にN個中1個でも対象の格子点があるかどうかが返るクエリがある。
このクエリを8000回まで用いて、N個の格子点の位置を特定せよ。

解法

矩形領域を縦または横に二分割していき、その中に1個以上対象の格子点があれば再帰的に分割していけばよい。

int N;
vector<pair<ll,ll>> ret;

int ask(int x1,int x2,int y1,int y2) {
	if(x2<x1||y2<y1) return 0;
	cout<<"? "<<x1<<" "<<x2<<" "<<y1<<" "<<y2<<endl;
	cin>>x1;
	return x1;
}

void dfs(int L,int R,int D,int U) {
	if(L>R) return;
	if(D>U) return;
	
	if(L==R&&U==D) {
		ret.push_back({L,D});
		return;
	}
	
	if(R-L>=U-D) {
		int M=(L+R)/2;
		if(ask(L,M,D,U)) dfs(L,M,D,U);
		if(ask(M+1,R,D,U)) dfs(M+1,R,D,U);
	}
	else {
		int M=(D+U)/2;
		if(ask(L,R,D,M)) dfs(L,R,D,M);
		if(ask(L,R,M+1,U)) dfs(L,R,M+1,U);
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	dfs(0,1000000,0,1000000);
	cout<<"! "<<ret.size()<<endl;
	FORR2(x,y,ret) cout<<x<<" "<<y<<endl;
	
}

まとめ

これは★2.5位でもいい気がするな…。