CF1924F Anti-Proxy Attendance

这是一个交互题！ 1048576 先生是那种讨厌浪费时间点名的老师。今天，他决定尝试一种新方法来点名。 他的班级里有 $n$ 名学生，学号从 $1$ 到 $n$。他知道今天恰好有 $1$ 名学生缺席。为了确定缺席的是谁，他可以向班级提出一些询问。每次询问，他可以给出两个整数 $l$ 和 $r$（$1\leq l\leq r\leq n$），所有学号在 $l$ 到 $r$ 之间（包含 $l$ 和 $r$）的学生会举手。他随后统计举手人数，以判断缺席学生的学号是否在这个区间内。 一切看起来都很顺利，直到他的助教注意到一个问题——学生们并不诚实！有些学号在给定区间内的学生可能不会举手，而有些学号不在区间内的学生可能会举手。但学生们不想引起太多怀疑。因此，对于某个询问 $(l,r)$，只可能出现以下 $4$ 种情况—— 1. 真阳性：有 $r-l+1$ 名学生在场，且有 $r-l+1$ 名学生举手。 2. 真阴性：有 $r-l$ 名学生在场，且有 $r-l$ 名学生举手。 3. 假阳性：有 $r-l$ 名学生在场，但有 $r-l+1$ 名学生举手。 4. 假阴性：有 $r-l+1$ 名学生在场，但有 $r-l$ 名学生举手。 在前两种情况下，学生们是诚实作答的；在后两种情况下，学生们是不诚实作答的。学生们可以自行决定他们的策略，1048576 先生并不知道。此外，学生们既不想引起怀疑，又想制造混乱。因此，他们的策略始终满足以下两个条件—— 1. 学生们不会连续 $3$ 次诚实作答。 2. 学生们不会连续 $3$ 次不诚实作答。 1048576 先生对学生们的行为感到沮丧。因此，他最多愿意标记 $2$ 名学生为缺席（尽管他知道实际上只有一人缺席）。如果实际缺席的学生在这两人之中，则点名成功。此外，由于上课时间有限，他最多只能提出 $ \lceil\log_{1.116}{n}\rceil-1 $ 次询问（虽然这个数字很奇怪，但就这样吧）。请你帮助他完成一次成功的点名。

首先读入一行，包含一个整数 $t$（$1\leq t\leq 2048$），表示你需要解决的独立测试用例的数量。 对于每个测试用例，首先读入一行，包含一个整数 $n$（$3\leq n\leq 10^5$）。然后你可以最多进行 $ \lceil\log_{1.116}{n}\rceil-1 $ 次询问。 每次询问，输出一行，格式为 "? l r"（不含引号），其中 $1\leq l\leq r\leq n$。然后读入一行，包含一个整数 $x$（$r-l\leq x\leq r-l+1$），表示本次询问中举手的学生人数。 要标记某个学生为缺席，输出一行，格式为 "! a"（不含引号），其中 $1\leq a\leq n$。然后读入一个整数 $y$（$y\in\{0,1\}$）。如果学号为 $a$ 的学生确实缺席，则 $y=1$，否则 $y=0$。注意，这个操作不计入询问次数，但每个测试用例最多只能进行 $2$ 次。 每个测试用例结束时，输出一行 "#"（不含引号）。然后继续解决剩余的测试用例。 如果你询问次数超过限制或询问不合法，将会得到 Wrong answer 判定。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。 输出答案后，别忘了输出换行并刷新输出缓冲区，否则会得到 Idleness limit exceeded 判定。刷新缓冲区的方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 注意，本题的评测器是自适应的，即答案可能会根据你的询问发生变化，但始终与之前所有询问的结果保持一致。 Hack 的输入格式 本题的测试用例既有非自适应评测器，也有自适应评测器。你可以使用非自适应评测器进行 Hack。 输入的第一行包含一个整数 $t$（$1\leq t\leq 2048$）。 每个测试用例的第一行包含三个整数 $g$、$n$ 和 $x$，其中 $g=1$（用于标识该测试用例使用非自适应评测器），$n$（$3\leq n\leq 10^5$）表示班级人数，$x$（$1\leq x\leq n$）表示缺席学生的学号。保证所有测试用例中 $n$ 的总和不超过 $10^5$。 每个测试用例的第二行包含一个字符串 $S$（$1\leq |S|\leq 120, S_i\in \{\texttt{T},\texttt{F}\}$）。该字符串表示诚实序列的模式。如果 $S_{(i-1)\bmod |S|+1}=\texttt{T}$，则第 $i$ 次询问学生们会诚实作答，否则会不诚实作答。保证不存在 $i$ 使得 $S_{(i-1)\bmod |S|+1}=S_{i\bmod |S|+1}=S_{(i+1)\bmod |S|+1}$。

（同上，见输入格式）

对于第一个测试用例，学号为 $2$ 的学生缺席，诚实序列（见 Hack 部分）为 TFFTFTTF。在你的程序执行过程中，该测试用例将使用非自适应评测器。 对于第二个测试用例，学号为 $4$ 的学生缺席，诚实序列为 FFTFTTFT。在你的程序执行过程中，该测试用例将使用自适应评测器。因此，实际答案可能会根据你的询问不同而变化，但始终与之前所有询问的结果保持一致。 由 ChatGPT 4.1 翻译