CSES 3139 - Hidden Permutation

1.0s 512M

有一個隱藏的排列 \(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\)。輸出這一行之後，你的程式必須結束。

每一行後面都要加上換行，而且每輸出一行之後都必須確保輸出已經送出（清空輸出緩衝區）。

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

說明：隱藏的排列是 \([3, 1, 2]\)。第一個詢問問 \(a_3 < a_2\) 是否成立，這不成立，所以答案是 NO。第二個詢問問 \(a_3 < a_1\) 是否成立，這成立，所以答案是 YES。

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。

題目頁說明