钓鱼网站制作者,wordpress插件音乐,宿迁建设局质安站网站,网页小游戏源码CF1063C Dwarves, Hats and Extrasensory Abilities
题意#xff1a;
首先题目会给出 n #xff0c;表示要输入多少点。 然后你输出n 个点的坐标#xff0c;每输出一个点会告诉你这个点的颜色是黑色或者白色。 最后你需要输出两个点的坐标代表一条直线#xff0c;这条直线…CF1063C Dwarves, Hats and Extrasensory Abilities
题意
首先题目会给出 n 表示要输入多少点。 然后你输出n 个点的坐标每输出一个点会告诉你这个点的颜色是黑色或者白色。 最后你需要输出两个点的坐标代表一条直线这条直线能够将你刚刚给出的点分成两份一份全都是黑色的点另一份全都是白色的点。
所有的点不能重叠所有点不能和最后输出的直线重叠每个点的黑白是随机给出的你需要保证你输出的数据有解并输出解。
题解
基本上交互都跟二分有关系 我一开始一点头绪都没有但我们可以这样想我们可以在一条线上选黑白点然后不断询问中点位置的颜色不断二分距离范围。 就比如如果(0,0)是白色下一次就问(1e9/2,0),如果是黑色就问(1e9/2/2,0)是什么颜色这样二分找可以将黑白分隔开,最后答案就是最后两个黑白快的中点 log2(1e9)29.897353,n最大30有可能会被卡?我提交后还真是在59这个点疯狂被卡我猜应该是二分到最后刚好用完没地方了导致最后答案与某个黑白块重叠这咋整 我突然想到一个方法我们最后的答案想的是二分最后一下得到一个整数解但题目要求你输出的是直线而这个直线与黑白所在直线的交点不用是整数点所以我们可以输出最后一个白块下方的点最后一个黑块上方的点这样的直线也正好平分黑白点而且不会占用整数点
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
mapint,intmp;
int main()
{rd_test();int n;cinn;int l0,r1e9;printf(0 1\n);mp[0]1;fflush(stdout);int lf-1,f-1,rf-1;string s;cins;if(sblack)lf0;else lf1;for(int i1;in;i){int midlr11;printf(%d 1\n,mid);fflush(stdout);mp[mid]1;cins;if(sblack)f0;else f1;if(flf)lmid;else if(frf)rmid;else if(rf-1){rff;rmid;}}printf(%d %d %d %d\n,l,0,r,2);//Time_test();
}
