Xoractive - 問題

Aidos 想出了一個謎題並挑戰 Temirulan 來解決它。他挑選了一個包含 $n$ 個相異非負整數的序列 $a$，編號從 $1$ 到 $n$：$a_1, a_2, \dots, a_n$。

Temirulan 可以詢問兩種類型的問題：

ask — 揭示給定序列中位置 $i$ 的數字。
get_pairwise_xor — 對於給定的相異整數索引序列：$i_1, i_2, \dots, i_k$，取得序列 $a$ 在這些索引處元素的兩兩 XOR 值集合，即 $\{a_{i_x} \oplus a_{i_y} \mid 1 \le x, y \le k\}$。

例如，假設 Aidos 挑選了序列 $[1, 5, 6, 3]$。那麼對於問題 ask(2)，Aidos 將回答數字 $5$；對於問題 get_pairwise_xor({3, 4})，Aidos 將回答序列 $[0, 0, 5, 5]$，因為：

Temirulan 無法解開這個謎題，你的任務是幫助他。請使用上述問題找出隱藏的序列。

你的提交程式不得從標準輸入讀取資料、列印至標準輸出，或與任何其他檔案互動。

你的任務是實作以下函式：int[] guess(int n)

你的函式可以呼叫以下函式：

int ask(int i)
- $i$：序列中數字的索引，$1 \le i \le n$。
- 該函式回傳隱藏序列中第 $i$ 個數字。
int[] get_pairwise_xor(int[] pos)
- pos：序列索引的非空列表。
- pos 中的所有元素必須是相異整數。
- 令 $k$ 為 pos 中的元素數量。則對於每個 $1 \le i \le k$，皆有 $1 \le pos_i \le n$。
- 該函式回傳一個包含 $k^2$ 個元素的排序列表：兩兩 XOR 值的集合，$\{a_{pos_x} \oplus a_{pos_y} \mid 1 \le x, y \le k\}$。

對於每個測試，你呼叫這兩個函式的總次數不得超過 $200$ 次。如果違反上述任何條件，你的程式將獲得 Wrong Answer 判決。否則，你的程式將獲得 Accepted 判決，且你的分數將根據 ask 和 get_pairwise_xor 函式的總呼叫次數計算（請參閱「子任務」章節）。

在此任務中，評測系統不是自適應的（adaptive）。這意味著序列 $a$ 在評測系統執行開始時就已固定，並不取決於你程式的呼叫。

(6 分) $n \le 4$
(94 分) 無額外限制。對於此子任務，你的分數計算方式如下。令 $q$ 為 ask 和 get_pairwise_xor 函式的總呼叫次數。
- 若 $q \le 15$，你的分數為 $94$。
- 若 $15 < q \le 40$，你的分數為 $84 - 2(q - 16)$。
- 若 $40 < q \le 50$，你的分數為 $35$。
- 否則，你的分數為 $0$。

請注意，每個子任務的分數為該子任務所有測試結果中的最低分數。

XOR 運算為位元互斥或（bitwise exclusive OR）。

假設隱藏序列 $a$ 為 $[1, 5, 6, 3]$。評測系統呼叫該函式。互動範例如下：

範例評測系統讀取輸入的格式如下：

你可以在系統中下載 xoractive.zip，其中包含 Java、C++11、FPC 和 Python 2 的範例。

上述提供了所有呼叫函式的範例。對於 Python 2，你必須實作函式 def guess(n, interactor)，其中 interactor 是被測試類別的實例。ask 和 get_pairwise_xor 是該類別的方法。

xoractive.zip 包含每種語言的解決方案範例。

對於 Java 語言的解決方案，檔案名稱和類別名稱必須分別命名為 Xoractive.java 和 Xoractive。

對於 Pascal 語言的解決方案，檔案必須命名為 xoractive.pas。

QOJ.ac