AT_arc154_d.[ARC154D] A + B > C ?

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) $，询问 $ P_i+P_j>P_k $ 是否成立。

请你求出 $ P_1,P_2,\dots,P_N $ 的全部值。

本题为交互题（你的程序需要与评测程序通过输入输出进行交互）。

首先，你的程序会从标准输入读入排列的长度 $ 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 $

无。

限制

• $ 1\le N\le 2000 $
• $ P $ 在程序与评测程序开始交互前已确定。

评测说明

• 每次输出后请务必刷新输出缓冲区，否则可能会因 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 $。实际排列为 $ (3,1,2,4) $，因此 AC。

由 ChatGPT 4.1 翻译