Dwarves, Hats and Extrasensory Abilities Codeforces - 1063C

https://codeforces.com/contest/1063/problem/C

首先可以想到一个简单做法：先钦定这个直线的斜率k=-1，然后设直线y=-x+b

设黑点放直线上方；如果已知(x,y)是黑点，那么y>-x+b,b<x+y

如果已知(x,y)是白点，那么b>x+y

可以二分b，对于每个b输出任意合法(x,y)满足x+y=b，然后根据结果更新b的范围

这样子初始时b可以为[1,2e9-1]，可以发现log2(2e9)超过30了

然而试一下可以发现这样子会A不掉。。。发现有时会刚好少1次机会

然后我就不会了...期间还尝试了一些乱搞，然而发现那么写除了让自己pretestpassed并且FST以外什么用也没有(提交后WA59)

看了题解，发现很简单：只要开始时询问一个角上的点，比如询问右上角，如果是黑色，那么仍然按上面方法，如果是白色，那么设直线上方应该放的点为白点，然后仍然按上面方法

哎，我还是太菜了

错误记录：

1.写成fflush(input)

2.CF不能只输出\n，必须手动fflush(output)

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 char tmp[],c;

 int n;

 int main()

 {

     int l,r,mid,t,i;

     scanf("%d",&n);

     printf("%d %d\n",,);

     fflush(stdout);

     scanf("%s",tmp);

     c=tmp[];

     if(n==)

     {

         printf("%d %d %d %d\n",,,,);

         return ;

     }

     l=;r=-;

     for(i=;i<=n;++i)

     {

         mid=l+((r-l)>>);

         t=mid/;

         printf("%d %d\n",t,mid-t);

         fflush(stdout);

         scanf("%s",tmp);

         if(tmp[]==c)    r=mid-;

         else    l=mid+;

     }

     mid=l+((r-l)>>);

     t=mid/;

     printf("%d %d %d %d\n",t,mid-t,t+,mid-t-);

     return ;

 }