201543: [AtCoder]ARC154 D - A + B > C ?

Problem Statement

PCT has a permutation $(P_1,P_2,\dots,P_N)$ of $(1,2,\dots,N)$. You are only informed of $N$.

You can ask him at most $25000$ questions of the following form.

• Specify a triple of integers $(i,j,k)$ such that $1 \le i,j,k \le N$ and ask whether $P_i + P_j > P_k$.

Find all of $P_1,P_2,\dots,P_N$.

Constraints

• $1 \le N \le 2000$
• $P$ is decided before the start of the interaction of your program and the judge.

Input and Output

This is an interactive task, where your program and the judge interact via input and output.

First, your program is given $N$, the length of the permutation, from Standard Input:

$N$

Then, you get to ask questions. Print your question to Standard Output in the following format: (There should be a newline at the end.)

? $i$ $j$ $k$

If the question is valid, the answer $ans$ will be given from Standard Input:

$ans$

Here, $ans$ is Yes or No.

If the question is malformed or judged invalid because you have asked more questions than allowed, -1 will be given from Standard Input:

-1

Here, the submission has already been judged incorrect. The judge will end the interaction at this point; preferably, your program should also quit.

Once you have identified all of $P_1, P_2, \dots, P_N$, print them to Standard Output in the following format: (There should be a newline at the end.)

! $P_1$ $P_2$ $\dots$ $P_N$

Judging

• Each time you print something, end it with a newline and flush Standard Output. Otherwise, you might get a TLE