题解 CF1773H【Hot and Cold】

赛时跟队友一起摆烂了，于是没做出来，回来补题。

如果询问到了答案，可以直接判断并退出，因此下文的询问过程并没有考虑这一点。

显然“\((1,1)\) 比 \((0,0)\) 离所求位置更近”对于几乎所有点成立，因此我们可以依次询问 \((0,0),(1,1),(0,0)\)，忽略第一次的回答，则后两次回答分别对应 Closer 和 Further，记为 \(c\) 和 \(f\)。我们说“几乎所有点”，因为存在两个反例 \((0,1),(1,0)\)。容易发现反例情况 \(c=f\)（因为其实都对应 At the same distance），此时把两种情况都问一下即可得到答案。

通过以上过程，我们排除了平凡情况，并确定了 \(c\) 和 \(f\)。考虑二分，设所求位置在 \((x_l,y_l)\sim(x_r,y_r)\) 的子矩形中，求出中点 \((x_m,y_m)\)，依次询问 \((x_m,y_m),(x_m+1,y_m),(x_m+1,y_m+1)\)，忽略第一次的回答，则后两次的回答分别可以使 \(x\) 和 \(y\) 的范围减半。于是我们可以在 \(3\lceil\log_210^6\rceil+4=64\) 次询问内确定所求点。

有两点需要注意：

• 可以发现询问次数上限卡得很紧，要精细实现不要写丑多询问。
• 需要特判当 \(x_m\) 或 \(y_m\) 恰好等于 \(10^6\) 的情况，此时会涉及到坐标 \(10^6+1\) 从而导致不合法询问。

// Problem: CF1773H Hot and Cold
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1773H
// Memory Limit: 1000 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

string c, f;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
string ask(int x, int y) {
	printf("%d %d\n", x, y);
	fflush(stdout);
	string res;
	getline(cin, res);
	return res;
}
bool success(string s) {
	return s.find('!') != string::npos;
}

int main() {
	if(success(ask(0, 0))) return 0;
	if(success(c = ask(1, 1))) return 0;
	if(success(f = ask(0, 0))) return 0;
	if(c == f) return assert(success(ask(0, 1)) || success(ask(1, 0))),0;
	int xl = 0, xr = 1000001, yl = 0, yr = 1000001;
	while(xl < xr || yl < yr) {
		int xm = (xl + xr) >> 1, ym = (yl + yr) >> 1;
		string res1, res2;
		if(success(ask(xm, ym))) return 0;
		if(xm == 1000000 && ym == 1000000) res1 = res2 = f;
		else if(xm == 1000000) {
			res1 = f;
			if(success(res2 = ask(xm, ym+1))) return 0;
		}
		else if(ym == 1000000) {
			if(success(res1 = ask(xm+1, ym))) return 0;
			res2 = f;
		}
		else {
			if(success(res1 = ask(xm+1, ym))) return 0;
			if(success(res2 = ask(xm+1, ym+1))) return 0;
		}
		if(res1 == c) xl = xm + 1;
		else xr = xm;
		if(res2 == c) yl = ym + 1;
		else yr = ym;
	}
	assert(success(ask(xl, yl)));
	return 0;
}