题解：CF1063C Dwarves, Hats and Extrasensory Abilities

· · 题解

CF1063C Dwarves, Hats and Extrasensory Abilities 题解

提供一个好想的方法。

思路

首先看到 n 不超过 30，坐标不超过 10^{9}，很容易想到把每一个点放在坐标轴上二分。

但是因为 2^{30} 已经超过了 10^{9}，直接二分肯定是不行的。考虑到题目中用一条线平分那么我们就可以把横纵两条轴都用上，范围直接翻倍，如下图所示。

不过由于画的线上不能有点，所以这样还是不行，所以我们把剩下两条边也算上，然后把点平均分配在图中的红边和黑边上二分，这样每条边上的二分次数直接减半。

这样在划定分割线时，直接将两条线段二分的中点连线即可，因为 2^{15}=32768，这样保证了线上绝对不会有点，这样就可以了。

代码

#include "bits/stdc++.h"
#define int long long
using namespace std;
int n, l, r, l2, r2;
string s;
signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    l = 1, r = 2e9 - 1, l2 = 1, r2 = 2e9 - 1;
    for(int i = 1;i <= n;i++)
    {
        if(i % 2)
        {
            int mid = (l + r) / 2;
            if(mid > (int)(1e9))
            {
                cout << format("1000000000 {}", mid - (int)(1e9)) << endl;
            }else
            {
                cout << format("{} 0", mid) << endl;
            }
            cin >> s;
            if(s == "black")
            {
                l = mid + 1;
            }else
            {
                r = mid;
            }
        }else
        {
            int mid = (l2 + r2) / 2;
            if(mid > (int)(1e9))
            {
                cout << format("{} 1000000000", mid - (int)(1e9)) << endl;
            }else
            {
                cout << format("0 {}", mid) << endl;
            }
            cin >> s;
            if(s == "black")
            {
                l2 = mid + 1;
            }else
            {
                r2 = mid;
            }
        }
    }
    int mid = (l + r) / 2, mid2 = (l2 + r2) / 2;
    if(mid > (int)(1e9))
    {
        cout << format("1000000000 {}", mid - (int)(1e9));
    }else
    {
        cout << format("{} 0", mid);
    }
    if(mid2 > (int)(1e9))
    {
        cout << format(" {} 1000000000", mid2 - (int)(1e9)) << endl;
    }else
    {
        cout << format(" 0 {}", mid2) << endl;
    }
    return 0;
}