CodeForces 1018B The hat

The hat

题解：

定义d[i]为第i个数和他对面的差值。

然后我们可以发现d[i]和d[i+1]的差值只会有3种情况2, -2, 0。

并且可以知道 d[i] = - d[i+n/2]

所以如果一开始n = 4 * k 即 d[1] 是偶数的话， 一定有d[i] = 0的情况。

如果d[l] > 0 && d[r] < 0 那么中间一定有一个d[mid] = 0.

所以我们求出1 和 1 + n/2的d值， 然后二分那段区间会有解就好了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int n;

int solve(int x){

    printf("? %d\n? %d\n", x, x + n/);

    fflush(stdout);

    int a, b;

    scanf("%d%d", &a, &b);

    if(a == b) {

        printf("! %d\n", x);

        fflush(stdout);

        exit();

    }

    a -= b;

    return (a > ) - (a < );

}

int main(){

    scanf("%d", &n);

    if(n%){

        puts("! -1");

        fflush(stdout);

        return ;

    }

    int l = , r = n/;

    int lv = solve(), rv = - lv;

    while(l <= r){

        int m = l+r >> ;

        int mv = solve(m);

        if(mv == lv) l = m+;

        else r = m - ;

    }

    return ;

}