[二分][精度][思维] codeforces1064E Dwarves, Hats and Extrasensory Abilities

http://codeforces.com/contest/1064/problem/E

又是喜闻乐见的交互+二分，这个已经在cf的讨论区被吐槽两次了，每次出交互题都是二分。。。我一开始没有搞懂题意，以为是你随便给他出点它会自动调整让点可以分为两片区域，后来才意识到他是给定了点的颜色分布，就是第几个点你只要问就是安排好的，也就是说这个需要你掌握问的点的坐标。。。

但是在不知道下一个点是什么的时候如何发问呢，首先想简化的过程，如果问的点全在一条线上会发生什么：假设左边为白点右边为黑，那么那个分界线一定是先往一个方向走了几步，然后又得回头往另一个方向走，如此反复。那么如何保证每次“回头”都可以有足够的余地让继续走下去而不与之前定好的界限相交？想到了一个叫二分的东西。。在倍增法的实现里其实就可以发现，他每次都会减半所以每次都不会覆盖到原来的部分。

但是这个题目直接二分又是有问题的，因为最多可以有30个点，而[log2(1e9)]==29，也就是说有一种情况可能最后会有俩点重合，为了避免这种情况可以先ask一个(0,0)，并且以此确定左半边的颜色，而不是像一开始说的一样自己定左右颜色。这样的话就剩下了29个点需要处理了，1e9的范围可以保证无论如何二分都可以达到没有任何两个点重合的结果。这样的话只需要在分界处的两个点之间画一条斜线就可以了。

因为这个29的坑wa了n发。。。

 

#include

using namespace std;
typedef long long LL;
const int maxn=2e3+4;
const int mod=998244353;

bool check(int x,int y)
{
    cout<>str;
    if(str=="white")
        return 1;
    else
        return 0;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    int mx=1e9;
    bool ib=true;
    string str;
    cin>>n;
    n--;
    if(check(0,1))
        ib=false;
    int l=0,r=mx,mid,pl=0,pr=mx;
    while(n--)
    {
        mid=(l+r)>>1;bool f=check(mid,1);
        if(f&&!ib||!f&&ib)
            l=mid;
        else
            r=mid;
    }
    cout<