ioicamp ioicamp-2026

本題請不要使用標準輸入輸出流，不過你仍然可以輸出除錯訊息至標準錯誤流（stderr）。

你的程式需要在一開始使用前置處理器引入 lib1436.h，詳細請參考範例實作。

你需要完成以下的一個函式：

void onexor();

• 在一筆測資中，該函數會被呼叫恰好 $Q = 10^ 5$ 次。
• 該函數沒有任何回傳值

每次呼叫 onexor，你可以呼叫以下函式若干次：

string Partition(string part);

• 參數 part 為一個長度為 16 的 01 字串，代表你想詢問的選擇方法，其中 part 的第 $i$ 個字元如果為 1 代表將編號 $i$ 的箱子移入儲藏室，如果為 0 代表將編號 $i$ 的箱子留在客廳。
• 該函數的回傳為一個字串，該字串必定為 QAQ 與 WAH 其中一個，如果回傳為 QAQ 代表這樣的選擇方法餅乾會被吃掉，如果回傳為 WAH 代表這樣的選擇方法餅乾不會被吃掉。
• 在一筆測資，onexor $Q$ 次呼叫中，Partition 總共最多只能呼叫 $5 \times 10^ 5$ 次
• 如果回傳為 WAH，judge 會認定該次測試成功，請在 onexor return 前不要再呼叫 Partition 函式。

假設該筆測資內 onexor 被呼叫兩次，第一次呼叫小章魚在編號 $1$ 的箱子，餅乾在編號 $2$ 的箱子，第二次呼叫小章魚在編號 $3$ 的箱子，餅乾在編號 $4$ 的箱子，那麼一個可能的互動為：

評測程式端	參賽者程式端
呼叫 onexor()。
	呼叫 Partition("1100000011110000")。
回傳 QAQ。
	呼叫 Partition("1000000000000000")。
回傳 WAH。
	onexor() 函式 return。
呼叫 onexor()。
	呼叫 Partition("0010000000000000")。
回傳 WAH。
	onexor() 函式 return。

• $Q = 10^ 5$
• 每筆測試中箱子數皆恰為 $16$

若你有至少一個測資沒有獲得 Accepted，那你的得分為 0 分，否則對於一筆測資，令 $S$ 為 Partition 在該筆測資中總共被呼叫幾次，則該筆測資的分數根據以下方式給分，你的得分為所有測資的分數的最小值。

令 $K$ 為最小滿足 $S \le \lceil Q \times (\sqrt K + \frac {e} {50}) \rceil$ 的正整數，

• 若 $K > 16$，那麼該筆測試為 0 分
• 若 $16 \ge K \ge 5$，該筆測試為 10 分
• 若 $K = 4$，該筆測試為 50 分
• 若 $3 \ge K \ge 1$，該筆測試為 100 分

範例評分程式有分三種測試模式，第一行請輸入一個數字 $x$ $ (1 \le x \le 3)$ 來代表要使用哪一種測試模式。

如果 $x = 1$，接下來請輸入一個正整數 $Q$，代表 onexor 總共被呼叫幾次。

接著輸入 $Q$ 行，每行為一個長度為 $16$ 的字串，字串由 $14$ 個 0，$1$ 個 1，$1$ 個 2 構成，字串第 $i$ 個字元代表編號 $i$ 的紙箱內是：沒有內容物、有小章魚、有餅乾傳送門。

如果 $x = 2$，不用再輸入任何內容，範例評分程式會自動幫你測試 $10^ 5$ 筆從所有可能的組合均勻隨機挑出的測試資料。

如果 $x = 3$，請輸入一個長度為 16 的字串，字串由 14 個 0，1 個 1，1 個 2 構成，字串第 $i$ 個字元代表編號 $i$ 的紙箱內是：沒有內容物、有小章魚、有餅乾傳送門，範例評分程式會幫你測試這個資料 $10^ 5$ 次。

如果沒有任何互動格式錯誤，範例評分程式會輸出一行：

Accepted: Q S r

其中 $Q$ 為 onexor 總共被呼叫了幾次，$S$ 為 Partition 總共被呼叫了幾次，$r$ 為 $\frac S Q$。

由於 Windows Defender 以及各種奇怪東西的限制，本題的範例編譯指令不提供 Windows 批次檔。編譯及測試教學請參考下列說明。

• 如果你的系統是 Linux 或 MacOS，你可以直接執行 compile.sh 編譯你的程式，編譯結果會是 onexor.exe，請直接用命令列執行該檔案。
• 如果你的系統是 Windows，你有以下的選擇：
  1. 本地測試時加入 #include "grader.cpp"，並且以單一檔案的編譯執行方式測試，請注意這一行上傳時需要刪除，否則你會獲得一個 Compile Error。
  2. 將 compile.sh 的變數替換後直接於命令列執行，請注意你需要確保 g++ 在系統的環境變數 PATH 中。
  3. 如果你的電腦已經有 WSL (Windows Subsystem for Linux)，你可以直接使用 WSL 並按照 Linux 的做法。
  4. 使用電腦教室的 Ubuntu（啟動時可以選擇系統）並按照 Linux 的做法。