这是一道交互题。
一共有 $n$ 个人做成一圈，他们的编号从 $1$ 到 $n$。
现在每个人的手里面都有一个数字 $a_i$ ，并且保证每个人与他周围两个人的数字差为 $1$ ，即 $\mid a_i-a_{i\pm 1}\mid =1$ ，特别地，编号为 $1$ 与 $n$ 的人也满足这个规则。
在这个圈里面，编号为 $i$ 的人的对面坐着的是编号为 $i+\frac{n}{2}$ 的人（其中 $i\le \frac{n}{2}$），现在要你找到哪个人与他对面坐着的那个人手中的数字一样。
在最开始，交互程序会给你一个 $n(2\mid n, n\le 10^5)$ ，表示这个圈里面的人数，然后你可以输出以下两种格式的操作：
? x表示你想询问位置为 $x$ 的人手中的数字，询问不可执行超过 $60$ 次；! x表示你的程序的答案，即满足 $a_x=a_{x+\frac{n}{2}}(x\le \frac{n}{2})$ ，特别地，如果找不到答案，则输出! -1；
对于操作 $1$ ，交互程序会输出一个整数 $a_x$ 表示 $x$ 编号的人手中的数字。
对于操作 $2$ ，如果你的答案是错误的，程序会直接退出，且测试结果为 Wrong Answer ，否则若无其他问题则测试结果为 Accepted 。
The hat
The hat
Created by LXC on Thu Feb 8 23:07:57 2024
https://codeforces.com/problemset/problem/1019/B
ranting: 2000
tag: binary search, interactive
problem
这是一道交互题。
一共有 $n$ 个人做成一圈，他们的编号从 $1$ 到 $n$。
现在每个人的手里面都有一个数字 $a_i$ ，并且保证每个人与他周围两个人的数字差为 $1$ ，即 $\mid a_i-a_{i\pm 1}\mid =1$ ，特别地，编号为 $1$ 与 $n$ 的人也满足这个规则。
在这个圈里面，编号为 $i$ 的人的对面坐着的是编号为 $i+\frac{n}{2}$ 的人（其中 $i\le \frac{n}{2}$），现在要你找到哪个人与他对面坐着的那个人手中的数字一样。
在最开始，交互程序会给你一个 $n(2\mid n, n\le 10^5)$ ，表示这个圈里面的人数，然后你可以输出以下两种格式的操作：
? x表示你想询问位置为 $x$ 的人手中的数字，询问不可执行超过 $60$ 次；! x表示你的程序的答案，即满足 $a_x=a_{x+\frac{n}{2}}(x\le \frac{n}{2})$ ，特别地，如果找不到答案，则输出! -1；
对于操作 $1$ ，交互程序会输出一个整数 $a_x$ 表示 $x$ 编号的人手中的数字。
对于操作 $2$ ，如果你的答案是错误的，程序会直接退出，且测试结果为 Wrong Answer ，否则若无其他问题则测试结果为 Accepted 。
solution
设$a_i - a_{i+\frac{n}{2}} = b_i$，可知$b_i = -b_{i+\frac{n}{2}}$，并且$b_i-b_{i+1} \in \lbrace -2, 0, 2\rbrace $，我们只需要找到$b_i = 0$的i即可
当存在$b_i$为奇数，所有$b_i$都为奇数。不存在答案。
否则一定存在答案，犹豫$b_i = x, b_{i+\frac{n}{2}} = -x$，在x为偶数的情况下从x到-x每次歩长为2，必定经过0。
$b_1$与$b_{1+\frac{n}{2}}$异号,从1到n/2之间进行二分查找一定能找到0
code
1 |
|