呢題係交互題。喺輸出每一行之後,請務必刷新輸出緩衝區。喺 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)嘅。