欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【交互题】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");
}