Nastia and a Hidden Permutation
Contest: Codeforces Round 720 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, interactive

This is an interactive problem!

Nastia has a hidden permutation $$$p$$$ of length $$$n$$$ consisting of integers from $$$1$$$ to $$$n$$$. You, for some reason, want to figure out the permutation. To do that, you can give her an integer $$$t$$$ ($$$1 \le t \le 2$$$), two different indices $$$i$$$ and $$$j$$$ ($$$1 \le i, j \le n$$$, $$$i \neq j$$$), and an integer $$$x$$$ ($$$1 \le x \le n - 1$$$).

Depending on $$$t$$$, she will answer:

- $$$t = 1$$$: $$$\max{(\min{(x, p_i)}, \min{(x + 1, p_j)})}$$$;
- $$$t = 2$$$: $$$\min{(\max{(x, p_i)}, \max{(x + 1, p_j)})}$$$.

You can ask Nastia at most $$$\lfloor \frac {3 \cdot n} { 2} \rfloor + 30$$$ times. It is guaranteed that she will not change her permutation depending on your queries. Can you guess the permutation?

Input format:
The input consists of several test cases. In the beginning, you receive the integer $$$T$$$ ($$$1 \le T \le 10\,000$$$) — the number of test cases.

At the beginning of each test case, you receive an integer $$$n$$$ ($$$3 \le n \le 10^4$$$) — the length of the permutation $$$p$$$.

It's guaranteed that the permutation is fixed beforehand and that the sum of $$$n$$$ in one test doesn't exceed $$$2 \cdot 10^4$$$.

Interaction format:
To ask a question, print "? $$$t$$$ $$$i$$$ $$$j$$$ $$$x$$$" ($$$t = 1$$$ or $$$t = 2$$$, $$$1 \le i, j \le n$$$, $$$i \neq j$$$, $$$1 \le x \le n - 1$$$) Then, you should read the answer.

If we answer with $$$−1$$$ instead of a valid answer, that means you exceeded the number of queries or made an invalid query. Exit immediately after receiving $$$−1$$$ and you will see the Wrong Answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

To print the answer, print "! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_{n}$$$ (without quotes). Note that answering doesn't count as one of the $$$\lfloor \frac {3 \cdot n} {2} \rfloor + 30$$$ queries.

After printing a query or printing the answer, do not forget to output 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

To hack the solution, use the following test format.

The first line should contain a single integer $$$T$$$ ($$$1 \le T \le 10\,000$$$) — the number of test cases.

For each test case in the first line print a single integer $$$n$$$ ($$$3 \le n \le 10^4$$$) — the length of the hidden permutation $$$p$$$.

In the second line print $$$n$$$ space-separated integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$), where $$$p$$$ is permutation.

Note that the sum of $$$n$$$ over all test cases should not exceed $$$2 \cdot 10^4$$$.

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

Note:
Consider the first test case.

The hidden permutation is $$$[3, 1, 4, 2]$$$.

We print: "? $$$2$$$ $$$4$$$ $$$1$$$ $$$3$$$" and get back $$$\min{(\max{(3, p_4}), \max{(4, p_1)})} = 3$$$.

We print: "? $$$1$$$ $$$2$$$ $$$4$$$ $$$2$$$" and get back $$$\max{(\min{(2, p_2)}, \min{(3, p_4)})} = 2$$$.

Consider the second test case.

The hidden permutation is $$$[2, 5, 3, 4, 1]$$$.

We print: "? $$$2$$$ $$$3$$$ $$$4$$$ $$$2$$$" and get back $$$\min{(\max{(2, p_3}), \max{(3, p_4)})} = 3$$$.

Example input:
2
4

3

2

5

3

Example output:
? 2 4 1 3

? 1 2 4 2

! 3 1 4 2

? 2 3 4 2

! 2 5 3 4 1

Editorial:
Solution $$$1$$$:
Let's fix $$$2$$$ indices $$$i$$$ and $$$j$$$ $$$(1 \le i, j \le n,$$$ $$$i \neq j)$$$. Then restore $$$p_{i}$$$ and $$$p_{j}$$$.
Let's assume we know the maximum element among $$$p_i$$$ and $$$p_j$$$: $$$mx = \max(p_i, p_j)$$$.
Now we can figure out where exactly the maximum is by asking the following query:
$$$val = \max{(\min{(mx - 1, p_i)}, \min{(mx, p_j)})}$$$.
There are $$$2$$$ cases:
1. $$$val = mx - 1$$$: it means $$$p_j \lt mx$$$, otherwise $$$val = \min{(mx, p_j)} = mx$$$.
2. $$$val = mx$$$: it means $$$p_j = mx$$$, because $$$\min{(mx - 1, p_i)} \lt mx$$$.
If we know where the maximum is located we easily can find the remaining element:
• if $$$p_i = mx$$$, then $$$p_j = \min{(\max{(1, p_j)}, \max{(2, p_i)})}$$$.
• if $$$p_j = mx$$$, then $$$p_i = \min{(\max{(1, p_i)}, \max{(2, p_j)})}$$$.
We can solve the problem if we know the $$$mx$$$. Let's find it:
$$$mx = \max{(\min{(n - 1, p_i)}, \min{(n, p_j)})}$$$
Take a look on the case when $$$mx = n - 1$$$. Here we cannot be sure that $$$mx = max(p_i, p_j)$$$. It's possible only if $$$p_i = n$$$. Thus if $$$mx = n - 1$$$ we spend an extra query to be sure that $$$p_i \neq n$$$. We will ask:
$$$val = \max{(\min{(n - 1, p_j)}, \min{(n, p_i)})}$$$
So, if $$$val = n$$$, then the value $$$p_i$$$ equlas to $$$n$$$, otherwise the value $$$mx = n - 1$$$ equals to the real maximum among $$$p_i$$$ and $$$p_j$$$.
As a result, we can restore any $$$2$$$ elements of the permutation.
Let's split our permutation into $$$\lfloor \frac {n} {2} \rfloor$$$ pairs and restore them independently of each other.
The total queries we perform is $$$\lfloor \frac {3 \cdot n} { 2} \rfloor + 2$$$. We spend $$$3$$$ operations to restore each of the pair of elements. And no more than $$$2$$$ extra queries to be sure that $$$mx$$$ is correct.
Solution $$$2$$$:
Let's find the maximum of the permutation and then restore the element $$$p_i$$$ $$$(1 \le i \le n)$$$ of the permutation by query:
$$$p_i = \min{(\max{(1, p_i)}, \max{(2, mx})}$$$.
To find the maximum element let's split the permutation into $$$\lfloor \frac {n} {2} \rfloor$$$ pairs and perform the following operation to each of them:
$$$mx = \max{(\min{(n - 1, p_i)}, \min{(n, p_j)})}$$$.
• if $$$mx = n$$$, then $$$j$$$ is the position with a maximum element.
• if $$$mx = n - 1$$$, then need to make sure that $$$p_i \neq n$$$. Let's make the same extra query as we do in the Solution 1.
Note that if you don't find the maximum element among the $$$\lfloor \frac {n} {2} \rfloor$$$, then it's in the remaining element when $$$n$$$ is odd.
The total queries we perform is n + $$$\lfloor \frac {n} { 2} \rfloor + 1$$$. We ask $$$\lfloor \frac {n} { 2} \rfloor + 2$$$ queries to find the maximum of the permutation and $$$n - 1$$$ quiries to restore the remaining elements.