D - A + B > C ? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

PCT 君は (1,2,\dots,N) の順列 (P_1,P_2,\dots,P_N) を持っています。あなたには N のみが伝えられます。

あなたは PCT 君に以下の質問を 25000 回以下行うことができます。

  • 1 \le i,j,k \le N を満たす整数の組 (i,j,k) を 1 個指定し、P_i + P_j > P_k かどうかを聞く。

P_1,P_2,\dots,P_N を全て求めてください。

制約

  • 1 \le N \le 2000
  • P はプログラムとジャッジの対話の開始前に決定される。

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）である。

まず、あなたのプログラムに標準入力から順列の長さ N が与えられる。

N

その後、あなたは質問を行うことが出来る。 質問は標準出力に以下の形式で出力せよ。(末尾に改行を入れること。)

? i j k

質問が正当な場合、その質問の答え ans が標準入力から与えられる。

ans

ここで、ans は Yes または No である。

質問のフォーマットが間違っている、または質問を規定の回数より多く行ったという理由で質問が不正と判断された場合、-1 が標準入力から与えられる。

-1

この時、提出はすでに不正解と判定されている。ジャッジプログラムはこの時点で対話を終了するため、あなたのプログラムも終了するのが望ましい。

P_1,P_2,\dots,P_N が全て分かったら、標準出力に以下の形式で出力せよ。(末尾に改行を入れること。)

! P_1 P_2 \dots P_N

ジャッジ

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush せよ。そうしなかった場合、ジャッジ結果が TLE となる可能性がある。
  • 答えを出力したら(または -1 を受け取ったら)直ちにプログラムを正常終了せよ。そうしなかった場合、ジャッジ結果は不定である。
  • 余計な改行は不正なフォーマットの出力とみなされることに注意せよ。

入出力例

以下は、N = 4,P=(3,1,2,4) の場合の入出力例です。

入力 出力 説明
4 N が与えられます。
? 1 2 3 1 個目の質問として、P_1 + P_2 > P_3 かどうかを聞きます。
Yes P_1 + P_2=4,P_3=2 であるため、返答は Yes です。
? 2 3 3 2 個目の質問として、P_2 + P_3 > P_3 かどうかを聞きます。
Yes P_2 + P_3=3,P_3=2 であるため、返答は Yes です。
? 2 3 4 3 個目の質問として、P_2 + P_3 > P_4 かどうかを聞きます。
No P_2 + P_3=3,P_4=4 であるため、返答は No です。
! 3 1 2 4 P_1,P_2,P_3,P_4 を出力します。実際に、P=(3,1,2,4) であるため、AC となります。

Score : 700 points

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 verdict.
  • After printing the answer (or receiving -1), immediately terminate the program normally. Otherwise, the verdict will be indeterminate.
  • Note that unnecessary newlines will be considered as malformed output.

Sample Interaction

Below is an interaction with N = 4 and P=(3,1,2,4).

Input Output Description
4 N is given.
? 1 2 3 As the first question, you ask whether P_1 + P_2 > P_3.
Yes We have P_1 + P_2=4 and P_3=2, so the answer is Yes.
? 2 3 3 As the second question, you ask whether P_2 + P_3 > P_3.
Yes We have P_2 + P_3=3 and P_3=2, so the answer is Yes.
? 2 3 4 As the third question, you ask whether P_2 + P_3 > P_4.
No We have P_2 + P_3=3 and P_4=4, so the answer is No.
! 3 1 2 4 You print P_1,P_2,P_3,P_4. We do have P=(3,1,2,4), so you get an AC.