ZigZagK的博客
[二分]Codeforces1064E【Dwarves, Hats and Extrasensory Abilities】题解
ZigZagK
2018年10月22日 14:53
Codeforces
查看标签

题目概述

交互题，有 $n$ 个点，你需要指定每个点的坐标 $(x,y)$ ，每次指定之后会告诉你这个点的颜色。你需要确定你的点的坐标使得你给出的点能被直线分成两半，输出这条直线。

解题报告

我是zz吧，我一直在想怎么确定两端的颜色然后二分。看了题解之后发现我为什么要先知道两端颜色呢？直接假装左边什么颜色右边什么颜色就好了……最后那条直线可以选左边最后一个颜色上方到右边第一个颜色下方。

示例程序

因为限制非常紧……所以要先来一次确定左边的颜色，这样要好一些（其实我也不知道哪里好了些）。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,L,R;char s[10];

inline int Ask(int x,int y) {printf("%d %d\n",x,y);fflush(stdout);scanf("%s",s);return s[0]=='b';}
int main(){
    scanf("%d",&n);L=0;R=1e9;bool fl=Ask(0,1);
    for (int i=2;i<=n;i++) {int mid=L+(R-L>>1);if (Ask(mid,1)^fl) R=mid; else L=mid;}
    printf("%d %d %d %d\n",L,0,R,2);fflush(stdout);return 0;
}
版权声明：本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处！