4940. Permutation

单点时限: 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:

  • $\fcolorbox{blue}{white}{$\texttt{?}\ i\ j$}$ — means you ask whether $a_i < a_j$, the program will return < if $a_i< a_j$, or > if $a_i> a_j$.
  • $\fcolorbox{blue}{white}{$\texttt{!}\ t_1\ t_2\ t_3\dots t_n$}$ — means you give the $n$ numbers $a_{t_1},a_{t_2},\cdots, a_{t_n}$, the program will judge you output and finish interaction.

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;
  • see the documentation for other languages.

样例

Input
2

>

<

>

>

>
Output
? 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.

14 人解决,43 人已尝试。

25 份提交通过,共有 344 份提交。

7.3 EMB 奖励。

创建: 2 年前.

修改: 2 年前.

最后提交: 2 年前.

来源: N/A

题目标签