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$），表示隐藏数组。

见输入格式说明。

在第一个样例中，交互过程如下： | Stdin | Stdout| 解释说明 | | --- | --- | --- | | 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$)。由于存在多个满足询问的数字数组，因此无法找到唯一答案。 在第二个样例中，交互过程如下： | 步骤 | Stdin | Stdout | 解释说明 | | --- | --- | --- | --- | | 1 | 6 | | 读取 $n = 6$。存在 $6$ 个隐藏的整数。 | | 2 | | ? 1 2 3 | 询问由 $a_1$，$a_2$ 和 $a_3$ 组成的三角形面积。 | | 3 | 0 | | 无法组成非退化三角形（即面积为 0）。 | | 4 | | ? 2 3 4 | 询问由 $a_2$，$a_3$ 和 $a_4$ 组成的三角形面积。 | | 5 | 0 | | 无法组成非退化三角形。 | | 6 | | ? 4 5 6 | 询问由 $a_4$，$a_5$ 和 $a_6$ 组成的三角形面积。 | | 7 | 0 | | 无法组成非退化三角形。 | | 8 | | ? 1 5 6 | 询问由 $a_1$，$a_5$ 和 $a_6$ 组成的三角形面积。 | | 9 | 63 | | 收到 $16\Delta^2 = 63$。因此面积 $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$。 | | 10 | | ? 3 5 6 | 询问由 $a_3$，$a_5$ 和 $a_6$ 组成的三角形面积。 | | 11 | 15 | | 收到 $16\Delta^2 = 15$。因此面积 $\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$。 | | 12 | | ? 1 2 4 | 询问由 $a_1$，$a_2$ 和 $a_4$ 组成的三角形面积。 | | 13 | 135 | | 收到 $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$，我们可以推断出多重集 $\left\{a_3, a_5, a_6\right\}$ 必须是 $\left\{2, 2, 1\right\}$。 根据步骤 $8$ 和 $9$，多重集 $\left\{a_1, a_5, a_6\right\}$ 必须是 $\left\{4, 4, 1\right\}$ 或 $\left\{3, 2, 2\right\}$。 由于 $\left\{a_3, a_5, a_6\right\}$ 和 $\left\{a_1, a_5, a_6\right\}$ 共享了 $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$ 能够同时满足步骤 $2, 3, 4, 5, 12, 13$ 中所做的全部询问。 在第三个样例中，一个满足询问的数组是 $[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$。