P12552 [UOI 2024] Points on a Line

这是一道交互题。 数轴上有 $n$ 个整数坐标的点 $x_1, x_2, \ldots, x_n$。保证对于所有 $1\le i\le n$ 都有 $1\le x_i\le n$。 当且仅当点 $x_k$ 位于由点 $x_i$ 和 $x_j$ 构成的线段上时，我们称点 $x_k$ 在点 $x_i$ 和 $x_j$ 之间。形式化地说，点 $x_k$ 在点 $x_i$ 和 $x_j$ 之间当且仅当 $x_i \leq x_k \leq x_j$ 或 $x_j \leq x_k \leq x_i$。 你需要找到任意两个下标 $i$ 和 $j$，使得所有 $n$ 个点都位于点 $x_i$ 和 $x_j$ 之间。 你可以使用以下查询：选择三个下标 ($i$, $j$, $k$) 并查询点 $x_k$ 是否在点 $x_i$ 和 $x_j$ 之间。 你最多可以使用 $22222$ 次查询。 保证点的坐标在交互开始前就已固定。换句话说，**交互器不是自适应的**。

第一行包含一个整数 $n$ ($3 \le n \le 2 \cdot 10^4$) —— 点的数量。

要发起查询，请输出 "$\tt{?}$ $i$ $j$ $k$" ($1 \le i, j, k \le n$)，然后输出换行符并执行 $\tt{flush}$ 操作。 作为查询的响应，评测程序将输出一个整数 $f$ ($f \in \{0,1\}$)。如果 $f = 1$，表示点 $x_k$ 在点 $x_i$ 和 $x_j$ 之间；如果 $f = 0$，则表示不在。 如果查询无效（即超过最大查询次数或查询参数无效），评测程序将输出 $\texttt{-1}$ 并终止。此时，程序应立即终止，否则会被判为 $\tt{Wrong Answer}$。 当你准备好给出答案时，请以 "$\tt{!}$ $i$ $j$" ($1 \leq i, j \leq n$) 的格式输出，其中 $i$ 和 $j$ 是所求点的下标。输出后终止程序。 $\tt{flush}$ 操作的具体实现方式如下： - C++：$\texttt{fflush(stdout)}$ 或 $\texttt{cout.flush()}$； - Java：$\texttt{System.out.flush()}$； - Pascal：$\texttt{flush(output)}$； - Python：$\texttt{sys.stdout.flush()}$。 可以参考给出的模板代码。

|4|| |:-:|:-:| ||? 1 4 2| |1|| ||? 1 4 3| |1|| ||! 1 4| 在示例中，点的坐标为 $x = [1, 2, 3, 4]$。 ### 评分标准 - （$17$ 分）：$n \le 20$； - （$16$ 分）：$n \le 100$； - （$30$ 分）：$n \le 10000$； - （$23$ 分）：$n \le 20000$，$x_i \le 2$； - （$10$ 分）：$n \le 12000$； - （$4$ 分）：无额外限制。 翻译由 DeepSeek V3 完成