Codeforces Round 922 (Div. 2) |
---|
Finished |
This is an interactive problem!
In the new round, there were $$$n$$$ tasks with difficulties from $$$1$$$ to $$$n$$$. The coordinator, who decided to have the first round with tasks in unsorted order of difficulty, rearranged the tasks, resulting in a permutation of difficulties from $$$1$$$ to $$$n$$$. After that, the coordinator challenged ace5 to guess the permutation in the following way.
Initially, the coordinator chooses a number $$$x$$$ from $$$1$$$ to $$$n$$$.
ace5 can make queries of the form: $$$?\ i$$$. The answer will be:
The task for ace5 is to guess the permutation in no more than $$$40n$$$ queries. Since ace5 is too busy writing the announcement, he has entrusted this task to you.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
The interaction between your program and the jury's program begins with reading a positive integer $$$n$$$ ($$$1 \leq n \leq 2000$$$) — the length of the hidden permutation.
To make a query, output a line in the format "? i", where $$$1 \leq i \leq n$$$.
As an answer, you will receive:
You can make no more than $$$40n$$$ queries. To output the answer, you need to print "! a_1 a_2 ... a_n", where $$$1 \leq a_i \leq n$$$, and all of them are distinct. Outputting the answer does not count as a query.
If your program makes more than $$$40n$$$ queries for one test case, or makes an invalid query, then the response to the query will be -1. After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.
After outputting a query, do not forget to print a newline and flush the output buffer. Otherwise, you will receive the verdict Presentation Error. To flush the buffer, use:
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$.
The interactor in this problem is not adaptive.
Hacks:
To make a hack, use the following format:
The first line contains a single integer $$$t$$$ — the number of test cases.
The description of each test case should consist of two lines. The first line contains the numbers $$$n$$$ and $$$x$$$ ($$$1 \leq x \leq n \leq 2000$$$) — the length of the hidden permutation and the initial value of the number $$$x$$$. The second line contains $$$n$$$ distinct numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the permutation that the jury should choose in this test case.
Sum of $$$n$$$ over all test cases should not exceed $$$2000$$$.
2 5 > = < = < < 2 >
? 4 ? 2 ? 1 ? 5 ? 1 ? 3 ! 2 4 1 5 3 ? 1 ! 2 1
In the first test, the hidden permutation is $$$a$$$ = [$$$2,4,1,5,3$$$], and the initial value of $$$x$$$ is $$$3$$$.
In the second test, the hidden permutation is $$$a$$$ = [$$$2,1$$$], and the initial value of $$$x$$$ is $$$1$$$.
Name |
---|