310993: CF1918E. ace5 and Task Order

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:

• $>$, if $a_i > x$, after which $x$ increases by $1$.
• $<$, if $a_i < x$, after which $x$ decreases by $1$.
• $=$, if $a_i = x$, after which $x$ remains unchanged.

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:

• ">", if $a_i$ > $x$, after which $x$ will increase by $1$.
• "<", if $a_i$ < $x$, after which $x$ will decrease by $1$.
• "=", if $a_i$ = $x$, after which $x$ will remain unchanged.

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:

• 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.

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$.