【交互题】Codeforces 1019B The hat
程序员文章站
2022-05-22 10:46:21
...
分析:
非常简单的交互题,二分答案的左端点位置(在[1,n/2]中)
由于每两个相邻的点值都相差1,所以可以把询问的值看作一个由-1或1组成的序列的前缀和。
答案就是要求两个前缀和相差为0,长度为n/2的区间。
所以二分的时候,如果当前区间的左端点值(即a[l+n/2]-a[l])与中间的值(a[mid+n/2]-a[mid])同号,则如果有答案,右端点的值(a[r+n/2]-a[r])一定与中间的值(a[mid+n/2]-a[mid])异号,每次忘异号的那个区间找即可。(因为异号的区间一定经过了0这个点)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define SF scanf
#define PF printf
#define MAXN 100010
using namespace std;
typedef long long ll;
int n,m,p,v,l,r;
int a[MAXN];
bool used[MAXN];
int ask(int x){
if(used[x])
return a[x];
used[x]=1;
PF("? %d\n",x);
fflush(stdout);
int l,r;
SF("%d",&l);
PF("? %d\n",x+n/2);
fflush(stdout);
SF("%d",&r);
if(l==r){
PF("! %d\n",x);
exit(0);
}
a[x]=r-l;
}
void que(int l,int r){
int mid=(l+r)>>1;
ll vall=ask(l);
ll valm=ask(mid);
ll valr=ask(r);
if(vall*valm<0)
que(l,mid);
else if(valm*valr<0)
que(mid+1,r);
}
int main(){
SF("%d",&n);
if(n%4){
PF("! -1");
return 0;
}
que(1,n/2);
PF("! -1");
}