链接: https://cses.fi/problemset/task/3139

板块: Interactive Problems

时限: 1.00 s ｜ 内存: 512 MB

题目描述

有一个隐藏的排列 $a_1, a_2,\dots, a_n$，由整数 $1, 2,\dots, n$ 组成。你的任务是求出这个排列。

为此，你可以进行提问：选择两个下标 $i$ 和 $j$，评测机将告诉你 $a_i < a_j$ 是否成立。

输入

这是一个交互题。你的程序将通过标准输入和输出与评测机进行交互。你应当先读取一个整数 $n$：排列的长度。

在你的回合中，你可以输出以下内容之一：

• ? i j，其中 $1 \le i, j \le n$：询问 $a_i < a_j$ 是否成立。若 $a_i < a_j$ 则评测机返回 YES，否则返回 NO。
• ! a_1 a_2 ... a_n：报告隐藏的排列为 $a_1, a_2,\dots, a_n$。输出此行后你的程序必须终止。

每行输出后都应跟一个换行符。你必须确保每行输出后都刷新缓冲区。

输出

参见上述交互协议。

数据范围

$1 \le n \le 1000$ 你最多可以进行 $10^4$ 次类型为 ? 的提问

样例

3
? 3 2
NO
? 3 1
YES
! 3 1 2

说明：隐藏的排列为 $[3, 1, 2]$。第一个问题询问 $a_3 < a_2$ 是否成立，结果为假，因此答案为 NO。第二个问题询问 $a_3 < a_1$ 是否成立，结果为真，因此答案为 YES。