单点时限: 10.0 sec
内存限制: 1024 MB
This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout)
, in Java — System.out.flush()
, in Pascal — flush(output)
and in Python — sys.stdout.flush()
.
Cuber QQ has a permutation of $1, 2, \dots, 3n$, denoted as $a_1, a_2, \dots, a_{3n}$. Your task is to pick up $n$ different numbers, and the sum of the chosen numbers should be larger than the sum of the rest numbers.
Of course, Cuber QQ will not directly tell you the permutation. He will allow you to give at most $6n$ queries. In each query, you can give two indexes $i$ and $j$, and then Cuber QQ will tell you whether $a_i < a_j$. Within the queries, you should finally give $n$ indexes denoting the numbers you want to choose.
All tests are guaranteed random and the number of tests is no more than $100$.
The interaction starts with reading one integer $n$ ($20000 \le n \le 50000$).
Then you can start the interaction. You can make queries like:
<
if $a_i< a_j$, or >
if $a_i> a_j$.You can ask at most $6n$ ?
queries.
After printing any query do not forget to print end of line and flush the output. Otherwise, you might 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;2 > < > > >
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 1 6 ! 1 3
The example is not in the tests. The permutation of example is $5,4,6,1,3,2$.
Note that the example interaction contains extra empty lines so that it’s easier to read. The real interaction doesn’t contain any empty lines and you shouldn’t print any extra empty lines as well.