P14195 [ICPC 2024 Hangzhou R] Identify Chord

$\textit{这是一个交互题。}$ Grammy 有一个包含 $n$ 个顶点的无向环图（$4 \le n \le 10^9$），顶点编号为 $1$ 到 $n$。一个无向环图是指有 $n$ 个顶点和 $n$ 条无向边，所有边首尾相连形成一个环。具体地，对于每个 $1 \le i \le n$，在顶点 $i$ 和顶点 $((i \bmod n)+1)$ 之间有一条双向边。 Grammy 觉得这个图太无聊了，于是她偷偷地选择了一对$\textit{不相邻}$的顶点，连上一条无向边（称为“弦”），使得该图现在有 $n$ 个顶点和 $n+1$ 条边。 你的任务是在不超过 $40$ 次查询内猜出这条弦的位置。每次查询，你可以给出两个顶点 $x$ 和 $y$，Grammy 会告诉你这两个顶点之间的最短路径包含的边数。 请注意，交互器是$\textit{非自适应的}$，也就是说弦的位置在交互开始前就被确定。

有多组测试数据。输入的第一行包含一个整数 $T$（$1 \le T \le 10^3$），表示测试数据组数。对于每组测试数据： 第一行为一个整数 $n$（$4 \le n \le 10^9$），表示顶点数。

每次查询，需要输出一行，首先输出 \texttt{?}，然后空格，然后输出两个顶点 $x$ 和 $y$（$1 \le x, y \le n$），用空格分隔。输出后需要刷新输出缓冲区，然后你的程序将读入一个整数，表示这两个顶点之间最短路经过的边数。 当你认为找到了弦的位置时，输出一行，首先输出 $\texttt{!}$，空格，然后输出两个顶点 $u$ 和 $v$（$1 \le u, v \le n$），表示弦连接了 $u$ 与 $v$。此时应立即刷新输出缓冲区，之后程序应读入一个整数 $r$（$r\in \{1,-1\}$），表示你的猜测是否正确。如果 $r=1$，表示猜测正确，应继续处理下一个测试数据（或者如果已经没有更多数据则直接退出）。否则，如果 $r=-1$，表示猜测错误，应立即退出程序，将获得 $\texttt{Wrong Answer}$ 判定。注意，猜测弦的位置不计入 $40$ 次查询次数。 在刷新输出缓冲区时，你可以使用： - $\texttt{fflush(stdout)}$（如果使用 $\texttt{printf}$）或 $\texttt{cout.flush()}$（如果使用 $\texttt{cout}$）在 C 和 C++ 中。 - $\texttt{System.out.flush()}$ 在 Java 中。 - $\texttt{stdout.flush()}$ 在 Python 中。

示例测试点中的图如下图所示： :::align{center}  ::: 由 ChatGPT 5 翻译