CSES 3228 - Permuted Binary Strings

有一個隱藏的排列 \(a_1, a_2,\dots, a_n\)，它是整數 \(1, 2,\dots, n\) 的一個排列。你的任務是找出這個排列。

為此你可以提出詢問：你可以選一個二進位字串 \(b_1b_2\dots b_n\)，然後會收到二進位字串 \(b_{a_1}b_{a_2}\dots b_{a_n}\)。

互動方式

這是一道互動題。你的程式透過標準輸入與標準輸出和評測程式互動。一開始你要先讀入一個整數 \(n\)：排列的長度。

輪到你時，你可以輸出下列其中一種：

• ? b_1b_2...b_n，其中 \(b_i\in\{0, 1\}\)：評測程式會回傳二進位字串 \(b_{a_1}b_{a_2}\dots b_{a_n}\)。

• ! a_1 a_2 ... a_n：回報隱藏的排列是 \(a_1, a_2,\dots, a_n\)。輸出這一行之後，你的程式必須結束。

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

互動範例

3
? 100
100
? 010
001
? 001
010
! 1 3 2

說明：隱藏的排列是 \([1, 3, 2]\)。第一個詢問中 \(b_1b_2b_3 = 100\)，評測程式回傳 \(b_{a_1}b_{a_2}b_{a_3} = b_1b_3b_2 = 100\)。第二個詢問中 \(b_1b_2b_3 = 010\)，評測程式回傳 \(b_1b_3b_2 = 001\)。

限制

• \(1 \le n \le 1000\)
• 型態 ? 的詢問最多 \(10\) 次

題目來源

CSES - Permuted Binary Strings

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