CF1847E.Triangle Platinum?

This is an interactive problem.

Made in Heaven is a rather curious Stand. Of course, it is (arguably) the strongest Stand in existence, but it is also an ardent puzzle enjoyer. For example, it gave Qtaro the following problem recently:

Made in Heaven has $n$ hidden integers $a_1, a_2, \dots, a_n$ ($3 \le n \le 5000$, $1 \le a_i \le 4$). Qtaro must determine all the $a_i$ by asking Made in Heaven some queries of the following form:

• In one query Qtaro is allowed to give Made in Heaven three distinct indexes $i$, $j$ and $k$ ($1 \leq i, j, k \leq n$).
• If $a_i, a_j, a_k$ form the sides of a non-degenerate triangle$^\dagger$, Made in Heaven will respond with the area of this triangle.
• Otherwise, Made in Heaven will respond with $0$.

By asking at most $5500$ such questions, Qtaro must either tell Made in Heaven all the values of the $a_i$, or report that it is not possible to uniquely determine them.

Unfortunately due to the universe reboot, Qtaro is not as smart as Jotaro. Please help Qtaro solve Made In Heaven's problem.

——————————————————————

$^\dagger$ Three positive integers $a, b, c$ are said to form the sides of a non-degenerate triangle if and only if all of the following three inequalities hold:

• $a+b \gt c$,
• $b+c \gt a$,
• $c+a \gt b$.

Interaction

The interaction begins with reading $n$ ($3 \le n \le 5000$), the number of hidden integers.

To ask a question corresponding to the triple $(i, j, k)$ ($1 \leq i \lt j \lt k \leq n$), output "? $i$ $j$ $k$" without quotes. Afterward, you should read a single integer $s$.

• If $s = 0$, then $a_i$, $a_j$, and $a_k$ are not the sides of a non-degenerate triangle.
• Otherwise, $s = 16 \Delta^2$, where $\Delta$ is the area of the triangle. The area is provided in this format for your convenience so that you need only take integer input.

If the numbers $a_i$ cannot be uniquely determined print "! $-1$" without quotes. On the other hand, if you have determined all the values of $a_i$ print "! $a_1$ $a_2$ $\dots$ $a_n$" on a single line.

The interactor is non-adaptive. The hidden array $a_1, a_2, \dots, a_n$ is fixed beforehand and is not changed during the interaction process.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages.

Hacks

You can hack a solution with the following input format.

The first line contains a single integer $n$ ($3 \le n \le 5000$) — the number of hidden integers.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 4$) — the hidden array.

这是一个交互式问题。

“天堂制造”是一种相当奇特的替身。当然，它（ arguably ）是现存最强的替身，但它同时也是一位热衷解谜的爱好者。例如，它最近向 Qtaro 提出了如下问题：

“天堂制造”隐藏了 $n$ 个整数 $a_1, a_2, \dots, a_n$（其中 $3 \le n \le 5000$，且 $1 \le a_i \le 4$）。Qtaro 必须通过向“天堂制造”提出若干查询来确定所有 $a_i$ 的值。每次查询的形式如下：

• 在一次查询中，Qtaro 可向“天堂制造”提供三个互不相同的下标 $i$、$j$ 和 $k$（满足 $1 \leq i, j, k \leq n$）；
• 若 $a_i, a_j, a_k$ 能构成一个非退化三角形$^\dagger$，“天堂制造”将返回该三角形的面积；
• 否则，“天堂制造”将返回 $0$。

Qtaro 至多可提出 $5500$ 次此类查询，之后必须要么向“天堂制造”报告全部 $a_i$ 的值，要么声明这些值无法被唯一确定。

不幸的是，由于宇宙重启，Qtaro 不再像乔鲁诺那般聪慧。请帮助 Qtaro 解决“天堂制造”的难题。

——————————————————————

$^\dagger$ 三个正整数 $a, b, c$ 被称为能构成一个非退化三角形，当且仅当以下三个不等式同时成立：

• $a+b \gt c$，
• $b+c \gt a$，
• $c+a \gt b$。

交互方式

交互开始时，首先读入整数 $n$（$3 \le n \le 5000$），即隐藏整数的个数。

要对三元组 $(i, j, k)$（其中 $1 \leq i \lt j \lt 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 ... 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$）—— 隐藏数组。

In the first example, the interaction process happens as follows:

Stdin

Stdout

Explanation

3

Read $n = 3$. There are $3$ hidden integers

? 1 2 3

Ask for the area formed by $a_1$, $a_2$ and $a_3$

63

Received $16\Delta^2 = 63$. So the area $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$

! -1

Answer that there is no unique array satisfying the queries.

From the area received, we can deduce that the numbers that forms the triangle are either ($4$, $4$, $1$) or ($3$, $2$, $2$) (in some order). As there are multiple arrays of numbers that satisfy the queries, a unique answer cannot be found.

In the second example, the interaction process happens as follows:

Step

Stdin

Stdout

Explanation

1

6

Read $n = 6$. There are $6$ hidden integers

2

? 1 2 3

Ask for the area formed by $a_1$, $a_2$ and $a_3$

3

0

Does not form a non-degenerate triangle

4

? 2 3 4

Ask for the area formed by $a_2$, $a_3$ and $a_4$

5

0

Does not form a non-degenerate triangle

6

? 4 5 6

Ask for the area formed by $a_4$, $a_5$ and $a_6$

7

0

Does not form a non-degenerate triangle

8

? 1 5 6

Ask for the area formed by $a_1$, $a_5$ and $a_6$

9

63

Received $16\Delta^2 = 63$. So the area $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$

10

? 3 5 6

Ask for the area formed by $a_3$, $a_5$ and $a_6$

11

15

Received $16\Delta^2 = 15$. So the area $\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$

12

? 1 2 4

Ask for the area formed by $a_3$, $a_5$ and $a_6$

13

135

Received $16\Delta^2 = 135$. So the area $\Delta = \sqrt{\frac{135}{16}} \approx 2.904738$

14

! 3 2 1 4 2 2

A unique answer is found, which is $a = [3, 2, 1, 4, 2, 2]$.

From steps $10$ and $11$, we can deduce that the the multiset \left{a_3, a_5, a_6\right} must be \left{2, 2, 1\right}.

From steps $8$ and $9$, the multiset \left{a_1, a_5, a_6\right} must be either \left{4, 4, 1\right} or \left{3, 2, 2\right}.

As \left{a_3, a_5, a_6\right} and \left{a_1, a_5, a_6\right} share $a_5$ and $a_6$, we conclude that $a_5 = a_6 = 2$, as well as $a_1 = 3$, $a_3 = 1$.

From steps $6$ and $7$, we know that $a_5 = a_6 = 2$, and $a_4$, $a_5$ and $a_6$ cannot form a non-degenerate triangle, hence $a_4 = 4$.

With all the known information, only $a_2 = 2$ satisfies the queries made in steps $2$, $3$, $4$, $5$, $12$ and $13$.

In the third example, one array that satisfies the queries is $[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$.

在第一个例子中，交互过程如下所示：

标准输入（Stdin）

标准输出（Stdout）

说明（Explanation）

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)$（顺序任意）。由于存在多个满足查询条件的数组，因此无法确定唯一解。

在第二个例子中，交互过程如下所示：

步骤（Step）

标准输入（Stdin）

标准输出（Stdout）

说明（Explanation）

1

6

读入 $n = 6$。共有 $6$ 个隐藏整数。

2

? 1 2 3

询问由 $a_1$、$a_2$ 和 $a_3$ 构成的三角形的面积。

3

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]$。