CF1847E Triangle Platinum?

这是一个交互题。 Made in Heaven 是一个非常奇特的替身。当然，它（可以说）是已知最强的替身，但它也是一个狂热的谜题爱好者。例如，它最近给 Qtaro 出了如下问题： Made in Heaven 拥有 $n$ 个隐藏的整数 $a_1, a_2, \dots, a_n$（$3 \le n \le 5000$，$1 \le a_i \le 4$）。Qtaro 需要通过向 Made in Heaven 提出如下形式的询问，确定所有 $a_i$ 的值： - 每次询问，Qtaro 可以给 Made in Heaven 三个不同的下标 $i$、$j$ 和 $k$（$1 \leq i, j, k \leq n$）。 - 如果 $a_i, a_j, a_k$ 能构成一个非退化三角形 $^\dagger$，Made in Heaven 会回复这个三角形的面积。 - 否则，Made in Heaven 会回复 $0$。 Qtaro 最多可以提出 $5500$ 次这样的询问，之后必须要么给出所有 $a_i$ 的值，要么报告无法唯一确定。 由于宇宙重启，Qtaro 没有 Jotaro 那么聪明。请你帮助 Qtaro 解决 Made in Heaven 的问题。 —————————————————————— $^\dagger$ 三个正整数 $a, b, c$ 能构成非退化三角形，当且仅当满足以下三个不等式： - $a + b > c$， - $b + c > a$， - $c + a > b$。

交互开始时，首先读入一个整数 $n$（$3 \le n \le 5000$），表示隐藏整数的个数。 每次询问 $(i, j, k)$（$1 \leq i < j < k \leq n$），输出一行 "? $i$ $j$ $k$"（不含引号）。随后，你应读入一个整数 $s$。 - 如果 $s = 0$，则 $a_i, a_j, a_k$ 不能构成非退化三角形。 - 否则，$s = 16\Delta^2$，其中 $\Delta$ 是三角形的面积。面积以此格式给出，便于你只需处理整数输入。 如果无法唯一确定所有 $a_i$，输出 "! $-1$"（不含引号）。如果你已经确定了所有 $a_i$ 的值，输出 "! $a_1$ $a_2$ $\dots$ $a_n$"（一行）。 交互器是非自适应的。隐藏数组 $a_1, a_2, \dots, a_n$ 在交互过程中是固定的，不会改变。 每次输出询问后不要忘记换行并刷新输出缓冲区，否则会因“Idleness limit exceeded”而被判为超时。具体刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 Hack 你可以用以下输入格式对解法进行 Hack。 第一行一个整数 $n$（$3 \le n \le 5000$），表示隐藏整数的个数。 第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 4$），表示隐藏数组。

见输入格式说明。

在第一个样例中，交互过程如下： StdinStdout说明3读入 $n = 3$，有 $3$ 个隐藏整数? 1 2 3询问 $a_1$、$a_2$、$a_3$ 能否构成三角形63收到 $16\Delta^2 = 63$，面积 $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$! -1回答无法唯一确定隐藏数组。由收到的面积可知，三角形的三边可能是 $(4, 4, 1)$ 或 $(3, 2, 2)$（顺序任意）。存在多组解，无法唯一确定。 在第二个样例中，交互过程如下： StepStdinStdout说明16读入 $n = 6$，有 $6$ 个隐藏整数2? 1 2 3询问 $a_1$、$a_2$、$a_3$ 能否构成三角形30不能构成非退化三角形4? 2 3 4询问 $a_2$、$a_3$、$a_4$ 能否构成三角形50不能构成非退化三角形6? 4 5 6询问 $a_4$、$a_5$、$a_6$ 能否构成三角形70不能构成非退化三角形8? 1 5 6询问 $a_1$、$a_5$、$a_6$ 能否构成三角形963收到 $16\Delta^2 = 63$，面积 $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$10? 3 5 6询问 $a_3$、$a_5$、$a_6$ 能否构成三角形1115收到 $16\Delta^2 = 15$，面积 $\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$12? 1 2 4询问 $a_3$、$a_5$、$a_6$ 能否构成三角形13135收到 $16\Delta^2 = 135$，面积 $\Delta = \sqrt{\frac{135}{16}} \approx 2.904738$14! 3 2 1 4 2 2唯一解为 $a = [3, 2, 1, 4, 2, 2]$。由第 10、11 步可知，$\{a_3, a_5, a_6\}$ 必为 $\{2, 2, 1\}$。 由第 8、9 步可知，$\{a_1, a_5, a_6\}$ 必为 $\{4, 4, 1\}$ 或 $\{3, 2, 2\}$。 由于 $\{a_3, a_5, a_6\}$ 和 $\{a_1, a_5, a_6\}$ 共享 $a_5$ 和 $a_6$，可知 $a_5 = a_6 = 2$，进而 $a_1 = 3$，$a_3 = 1$。 由第 6、7 步可知 $a_5 = a_6 = 2$，$a_4$、$a_5$、$a_6$ 不能构成三角形，因此 $a_4 = 4$。 结合所有已知信息，只有 $a_2 = 2$ 满足所有已知询问。 在第三个样例中，满足条件的数组之一为 $[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$。 由 ChatGPT 4.1 翻译