本題為互動題。在輸出每一行之後,請務必重新整理輸出緩衝區。在 C++ 中可以使用 cout << flush;在 Java 中可以使用 System.out.flush();在 Python 中可以使用 sys.stdout.flush()。你必須嚴格遵守「互動格式」部分的說明,否則可能會收到 Wrong Answer、Time Limit Exceeded 或其他評判結果。
既然所有的任務都以神話中的矮人為主角,那麼終於思考一些具體實際的東西或許是值得的。
有一個長度為 $N$ 的隱藏序列 $A$,由範圍在 $[0, 2^N - 1]$ 內的整數組成。你的任務是透過有限次數的查詢來恢復它。在每次查詢中,你提供一個長度為 $N$、元素範圍在 $[0, 2^N - 1]$ 內的序列 $B$。回應的計算方式如下:
- 建立序列 $C$,其中 $C$ 的第 $i$ 個元素是 $A$ 與 $B$ 的第 $i$ 個元素的按位元互斥或(bitwise xor)。我們以 $\oplus$ 表示互斥或。
- 建構集合 $S$,作為對 $C$ 中某個元素子集進行互斥或所能得到的所有數值的集合。特別地,對於空子集,互斥或結果為 $0$。
- 查詢的答案為 $|S|$。
例如,若 $A = (1, 4, 3)$ 且 $B = (0, 4, 7)$,則 $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ 且 $S = \{0, 1, 4, 5\}$,因此答案為 $4$。
兩個數 $x$ 與 $y$ 的按位元互斥或在第 $i$ 個位元為 $1$,若且唯若 $x$ 與 $y$ 中恰好有一個數的第 $i$ 個位元為 $1$。例如,$5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$。在 C++ 與 Python 中,互斥或是運算子 ^。
互動格式
序列 $A$ 在一開始就是固定的,且不取決於所做的查詢。
首先,讀取一行,包含一個整數 $1 \le N \le 60$。接著你可以進行查詢。
若要進行查詢,請印出一行,包含 ? 後接 $N$ 個範圍在 $[0, 2^N - 1]$ 內的整數。作為回應,讀取一個整數作為答案。
準備好後,印出 ! 後接隱藏序列的 $N$ 個整數。接著你的程式應立即結束,不要再有進一步的輸出。
請記住在每次查詢後以及輸出答案後重新整理輸出緩衝區。在數字與 ?、! 符號之間留出空格。
範例
輸入格式 1
3 4 8
輸出格式 1
? 1 2 3 ? 0 0 0 ! 1 3 4
說明
範例互動的說明:
$N = 3$
查詢 ? 1 2 3:$B = (1, 2, 3)$,$C = (1 \oplus 1, 3 \oplus 2, 4 \oplus 3) = (0, 1, 7)$,$S = \{0, 1, 6, 7\}$,答案為 $4$。
查詢 ? 0 0 0:$B = (0, 0, 0)$,$C = (1 \oplus 0, 3 \oplus 0, 4 \oplus 0) = (1, 3, 4)$,$S = \{0, 1, \dots, 7\}$,答案為 $8$。
輸出 ! 1 3 4:隱藏序列為 $A = (1, 3, 4)$。
本地測試
在「檔案」部分,你可以找到包含範例測試和評分器 grader.cpp 的 B.zip。若要測試你的解答,請先編譯它,然後將測試名稱和你的可執行檔傳遞給編譯後的 ./grader:
./grader [test] [executable]
例如:./grader 0b.in ./abc
範例評分器不保證與官方評分器的行為完全一致。然而,兩者都不是自適應(adaptive)的。