Triangle Platinum?
Contest: Codeforces Round 882 (Div. 2)
Difficulty rating: 2900
Tags: brute force, combinatorics, implementation, interactive, math, probabilities

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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

StdinStdoutExplanation3Read $$$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:

StepStdinStdoutExplanation16Read $$$n = 6$$$. There are $$$6$$$ hidden integers2? 1 2 3Ask for the area formed by $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$30Does not form a non-degenerate triangle4? 2 3 4Ask for the area formed by $$$a_2$$$, $$$a_3$$$ and $$$a_4$$$50Does not form a non-degenerate triangle6? 4 5 6Ask for the area formed by $$$a_4$$$, $$$a_5$$$ and $$$a_6$$$70Does not form a non-degenerate triangle8? 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]$$$.

Example input:
3

63

Example output:
? 1 2 3

! -1

Example input:
6

0

0

0

63

15

135

Example 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

Editorial:
First, notice that we can uniquely determine the multiset of numbers any three $$$a_i, a_j, a_k$$$ except for the collision between triples $$$(1, 4, 4)$$$ and $$$(2, 2, 3)$$$. The issue is that even if we know the multiset we cannot always uniquely determine $$$a_i, a_j, a_k$$$.
But what if all the elements of the multiset are equal? Then each element obviously has to be equal to the value of the multiset. So if for some three distinct $$$i, j, k$$$ the area of $$$a_i, a_j, a_k$$$ is one of $$$\sqrt{3}/4, \sqrt{3}, 9\sqrt{3}/4, 4\sqrt{3}$$$, then they are all equal to $$$1, 2, 3$$$ or $$$4$$$ respectively, depending on the area.
Let us say we knew that $$$a_i = a_j = a_k = C$$$ for some $$$C \in [1, 4]$$$ after asking $$$q$$$ queries. By querying $$$(i, j, x)$$$ for every $$$x$$$ other than $$$i, j$$$ we can obtain the area of $$$C, C, a_x$$$ for each $$$x$$$. This will allow us to uniquely determine each $$$a_x$$$. But wait! There is an important edge case here. We also require $$$C, C, a_x$$$ to form a valid triangle.
If $$$C \geq 2$$$, this is not an issue because $$$2, 2, 4$$$ can be just assigned an area of "$$$0$$$" and we can still uniquely retrieve the values. So using this procedure, it takes us $$$q+n-3$$$ queries to determine all the values.
The only possibility remaining is when $$$C = 1$$$. In this case, the issue is that only $$$[1, 1, 1]$$$ let us know the value of $$$a_x$$$. When $$$a_x > 1$$$, it's impossible to distinguish between $$$a_x = 2, 3, 4$$$. So if we asked all questions, we would know which indices have value $$$> 1$$$ and which indices have a value of $$$1$$$.
Now if we could find two equal elements among these indices with value $$$> 1$$$, we can repeat a similar linear scan as above and find all values. But how do we find two equal values? Notice that every value is among $$$2, 3, 4$$$. So if we had $$$ \geq 4$$$ such indices with value $$$ > 1$$$ some two of them would be equal, and we could find them by bruting queries of the form $$$(i, m_1, m_2)$$$ over all pairs of indices $$$m_1, m_2$$$ with value $$$> 1$$$.
After this we can then again query all the other $$$> 1$$$ indices and find answer. This would take around $$$q+n'+2(n-n')-\mathcal O(1)$$$ queries, where $$$n'$$$ is the number of ones. Unfortunately this would QLE if $$$n'$$$ were around $$$n/2$$$.
How do we fix this? The answer is surprisingly simple. When we were finding indices with value $$$ > 1$$$ we simply stop the minute we have at least $$$4$$$ such indices (it's ok even if we don't).
Now we brute over all pairs. If we find two equal, we are done within at most $$$q+n+16$$$ queries. On the other hand if we cannot find two equal it means that we can never distinguish between them. This is because any query of the form $$$(1, x, y)$$$ where $$$x \ne y$$$ are both $$$\geq 2$$$ is always a degenerate query hence will have answer $$$0$$$. So if we do not find two equal, we will print $$$-1$$$.
After all this work, there are still a few details left. First, $$$q$$$ must be small. Otherwise all the above work is useless. Second there should be three equal elements in the first place.
The first observation is that if $$$n \geq 9$$$ then by Piegonhole Principle, some $$$\lceil n/4 \rceil \geq 3$$$ must be equal. So if $$$n \geq 9$$$ then by bruting over all $$$1 \leq i < j < k \leq 9$$$ triples $$$(i, j, k)$$$ we can always find some three equal. Here we would have $$$q = {9 \choose 3} = 84$$$ and we are asking at most $$$n+84+16$$$ queries, which fits comfortably.
But what if $$$n < 9$$$? In this case we can simply brute all possible $$${9 \choose 3} = 84$$$ queries and then for each of the $$$4^n$$$ arrays possible check if the triples of that array match with the query answers obtained here. If there is exactly one such array, we have found it and we can print it, otherwise we print $$$-1$$$ because it is not possible to uniquely determine the values of the array. Notice that this takes at most $$$4^8 \cdot {8 \choose 3}$$$ operations, which is around $$$3.7 \cdot 10^6$$$ which fits in the TL.
This solves the problem.
You might wonder why $$$5500$$$ queries were allowed even though the above solution does not use more than around $$$5100$$$ queries. This is because we allowed randomisation as a valid way of finding three equal values $$$a_i, a_j, a_k$$$. Suppose there are $$$c_1, c_2, c_3, c_4$$$ counts of $$$1, 2, 3, 4$$$ respectively. If we randomly queried a triple $$$(i, j, k)$$$ each time, the probability all would be equal is precisely: $$$$$$\frac{{c_1 \choose 3}+{c_2 \choose 3}+{c_3 \choose 3}+{c_4 \choose 3}}{{n \choose 3}}$$$$$$ It is easy to see that the above is minimised when the $$$c_i$$$ are roughly equal. When $$$n \geq 30$$$, the above is at most $$$\frac{1}{17}$$$, so we will find a equal triple very quickly. The other case is when $$$n < 30$$$. In this case, since $$${30 \choose 3} < 5500$$$, we can simply query every triple and solve directly by finding three equal instead of relying on randomness. This sort of a method gives $$$q \leq 400$$$ with very high probability, so it will still pass with at most $$$5500$$$ queries.