Universal Cup Judging System

Universal Cup

Limite de temps : 1.0 s Limite de mémoire : 256 MB Points totaux : 100 Interactif
Statistiques

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