Universal Cup Judging System

Universal Cup

时间限制: 1.0 s 内存限制: 256 MB 总分: 100 交互
统计

本題為互動題。在輸出每一行之後,請務必重新整理輸出緩衝區。在 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)的。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.