题解 CF1773H【Hot and Cold】

rui_er · 2023-01-25 19:33:56 · 题解

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

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

显然“(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;
}