cf1064E. Dwarves, Hats and Extrasensory Abilities(二分 交互)

题意

题目链接

\(n\)次操作,每次你给出一个点的坐标,系统会返回该点的颜色(黑 / 白),程序最后输出一条直线把所有黑点和白点分隔开

Sol

一个很直观的想法:首先询问\((dx, 0)\),然后每次询问二分中点,根据与第一次询问得到的字符串的关系不断调整二分范围

但是这样会被卡,我修改了两个地方才过。

  1. 二分调整边界的时候直接设\(l = mid\)或\(r = mid\),因为我们最后得到的不是一个精确解,所以这样写是可以的
  2. 最后输出直线的时候加一个偏移量,也就是输出一条斜线

具体看代码

/*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/hash_policy.hpp>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
#define LL long long 
#define ull unsigned long long 
#define rg register 
#define pt(x) printf("%d ", x);
#define Fin(x) {freopen(#x".in","r",stdin);}
#define Fout(x) {freopen(#x".out","w",stdout);}
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? EOF : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
//char obuf[1<<24], *O = obuf;
//void print(int x) {if(x > 9) print(x / 10); *O++ = x % 10 + '0';}
//#define OS  *O++ = ' ';
//#define fout fwrite(obuf, O-obuf, 1 , stdout);
using namespace std;
//using namespace __gnu_pbds;
const int MAXN = 2005, INF = 1e9 + 10, mod = 1e9 + 7;
const int D[] = { -1, 1};
const double eps = 1e-9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int N, Dx = 23333;
string s, pre;

main() {
    N = read();
    int l = 0, r = 1e9;
    printf("%d 0\n", Dx);
    fflush(stdout);
    cin >> pre;
    int ans = 0;
    for(int i = 2; i <= N; i++) {
        int mid = l + r >> 1;
        printf("%d %d\n", Dx, mid);
        fflush(stdout);
        cin >> s;
        if(s != pre) r = mid;
        else l = mid, ans = mid;
    }
    
    printf("%d %d %d %d", Dx - 3, ans, Dx + 3, ans + 1);
    return 0;
}
/*
5
black
black
white
white
black
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏阮一峰的网络日志

排版六原则

几天后,就收到了秋叶老师的来信,希望与我探讨一些设计问题。他写过一本畅销书《说服力-让你的PPT会说话》,眼下正在写续集。

12220
来自专栏阮一峰的网络日志

带字幕的Youtube

现在有人就制作了一个网站YouTube Subtitle Editor,专门为Youtube加字幕。你可以先看一段动画片《蜘蛛人》的主题歌,体验一下效果。

49820
来自专栏阮一峰的网络日志

约翰·霍普金斯医学院的声明

14420
来自专栏跟着阿笨一起玩NET

js的alert和confirm美化

window对象的alert和confirm标准方法在不同浏览器的显示效果不太相同,有个相同点是都不是很美观。我们的想法是使用js和css分别仿照它们,提供另一...

30920
来自专栏服务端技术杂谈

去解决更多的问题,而不是如何最好地解决一个问题

有些人非常勤奋,别人休息和娱乐的时候,都在工作学习。但是努力了一辈子,人生也没有显著的提升,就像报道里经常说的:"某某在平凡的岗位上,勤勤恳恳工作了一辈子"。

13640
来自专栏老九学堂

揭秘!程序员为什么会一直加班加班...

14920
来自专栏前端侠2.0

td在relative模式下,IE9不显示border,chrome正常显示边框

百度上怎么也搜不出答案,很奇怪的问题。在IE9的 F12调试中,明明td有1个像素的边框,偏偏不显示。

14910
来自专栏凌帅的阅读思考与实践

【投资中的那些坑】开栏语

很多人在投资中喜欢财聚人聚,财散人散,总往有钱的地方钻营。就象游牧民族,哪里水草肥美,就到哪里去。一旦情况不好,就会迅速退场。只能同甘,不能共苦。

14630
来自专栏大数据文摘

业界 | 如何像程序员一样思考

即使你的运气一向很好,这种方法也并不值得使用。事实上,它可能是最糟糕的解决方法,因为会浪费大量的时间。

10810
来自专栏跟着阿笨一起玩NET

ASP.NET web.config中<customErrors>节点说明

customErrors>节点用于定义一些自定义错误信息的信息。此节点有Mode和defaultRedirect两个属性,其中defaultRedirect属性...

8310

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励