310533: CF1847E. Triangle Platinum?

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

E. Triangle Platinum?time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 > c$,
  • $b+c > a$,
  • $c+a > 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 < j < 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.

ExamplesInput
3

63
Output
? 1 2 3

! -1
Input
6

0

0

0

63

15

135

Output
? 1 2 3

? 2 3 4

? 4 5 6

? 1 5 6

? 3 5 6

? 1 2 4

! 3 2 1 4 2 2
Input
15

3

3

3

3

3

0

Output

? 1 2 3

? 4 6 7

? 8 9 10

? 11 12 13

? 13 14 15

? 4 5 6

! -1
Input
15

3

15

0

3

3

3

Output

? 1 2 3

? 3 4 5

? 4 5 6

? 7 8 9

? 10 11 12

? 13 14 15

! 1 1 1 2 2 4 1 1 1 1 1 1 1 1 1 1
Input
10

3

48

3

48

63

0


Output
? 1 3 5

? 4 6 8

? 1 5 9

? 6 8 10

? 4 2 6

? 7 10 8

! 1 3 1 2 1 2 4 2 1 2
Note

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

StdinStdoutExplanation
3Read $n = 3$. There are $3$ hidden integers
? 1 2 3Ask for the area formed by $a_1$, $a_2$ and $a_3$
63Received $16\Delta^2 = 63$. So the area $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$
! -1Answer 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:

StepStdinStdoutExplanation
16Read $n = 6$. There are $6$ hidden integers
2? 1 2 3Ask for the area formed by $a_1$, $a_2$ and $a_3$
30Does not form a non-degenerate triangle
4? 2 3 4Ask for the area formed by $a_2$, $a_3$ and $a_4$
50Does not form a non-degenerate triangle
6? 4 5 6Ask for the area formed by $a_4$, $a_5$ and $a_6$
70Does not form a non-degenerate triangle
8? 1 5 6Ask for the area formed by $a_1$, $a_5$ and $a_6$
963Received $16\Delta^2 = 63$. So the area $\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$
10? 3 5 6Ask for the area formed by $a_3$, $a_5$ and $a_6$
1115Received $16\Delta^2 = 15$. So the area $\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$
12? 1 2 4Ask for the area formed by $a_3$, $a_5$ and $a_6$
13135Received $16\Delta^2 = 135$. So the area $\Delta = \sqrt{\frac{135}{16}} \approx 2.904738$
14! 3 2 1 4 2 2A 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]$.

Input

暂时还没有翻译

Output

题目大意:
这是一个交互式问题。给定一个整数n(3≤n≤5000),表示有n个隐藏的整数a_1, a_2, ..., a_n(1≤a_i≤4)。通过最多5500次询问,Qtaro需要确定所有的a_i值,或者报告无法唯一确定它们。每次询问Qtaro可以给出三个不同的索引i, j, k(1≤i
输入输出数据格式:
输入:第一行是一个整数n,表示隐藏整数的数量。随后的每一行对应一次交互,如果是一次查询,则格式为"? i j k",如果是报告结果,则格式为"! a_1 a_2 ... a_n"。
输出:对于每个查询,输出对应的结果,如果可以构成三角形,则输出面积s;否则输出0。如果确定了所有a_i的值,则输出"! a_1 a_2 ... a_n";如果无法唯一确定,则输出"! -1"。

注意:每次查询后需要输出换行符并刷新输出,否则会超时。题目大意: 这是一个交互式问题。给定一个整数n(3≤n≤5000),表示有n个隐藏的整数a_1, a_2, ..., a_n(1≤a_i≤4)。通过最多5500次询问,Qtaro需要确定所有的a_i值,或者报告无法唯一确定它们。每次询问Qtaro可以给出三个不同的索引i, j, k(1≤i

加入题单

上一题 下一题 算法标签: