ioicamp ioicamp-2025

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

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

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

std::vector<int> guessstone(int n);

• 在一筆測試資料中，guessstone 會被呼叫恰一次。
• n 代表石頭的總數。
• 石頭的編號為 $0, 1, \ldots, n - 1$。
• 回傳值必須為一個長度為 $n$ 的陣列，其中若第 $i$ 個石頭為黑色，則陣列第 $i$ 項為 1，否則為 0。

你可以呼叫以下函式：

int query(std::vector<int> S);

• 引數 $S$ 需滿足 $|S| > 0$、$\forall s \in S, 0 \leq s < n$ 且 $S$ 內沒有相同的元素。
• 回傳值是一個整數，表示該集合中黑色石頭的數量。
• 每次詢問會增加 $\frac{1}{|S|}$ 的 Cost。
• query 不得被呼叫超過 $\textbf{20\ 000}$ 次。

如果任意一個條件沒有被滿足，你的程式會被判斷為 Wrong Answer 並且獲得 0 分，否則，你的程式將依照 Scoring 中的敘述評分。

假設 $n = 4$，一個被判斷為 Accepted 的範例互動狀況如下：

評測程式端	參賽者程式端
呼叫 guessstone(4)。
	呼叫 query({0})。
回傳 1。
	呼叫 query({1, 2})。
回傳 0。
	呼叫 query({3})。
回傳 1。
	回傳 {1, 0, 0, 1}。

• $1 \leq n \leq 2000$
• 石頭顏色不會隨著互動過程而改變。

假設在所有測試資料中，你呼叫 query 所造成的總 Cost 為 $C$，你的得分 $S$ 由下列方式計算：

• 如果 $C \leq 10$， $$S = 100$$
• 否則， $$S = 0$$

範例評分程式以下列方式輸入：

• line $1$: $n$
• line $2$: $a_0$ $a_1$ $\ldots$ $a_{n - 1}$

其中若第 $i$ 顆石頭為黑色，則 $a_i = 1$，否則 $a_i = 0$。

範例評分程式以下列方式輸出：

如果你的程式被判斷為 Accepted，範例評分程式會輸出 Accepted: C，其中 C 為呼叫 query 所造成的總 Cost。接著輸出一行，該行有 $n$ 個整數，其中第 $i$ 個整數為你回傳的第 $i$ 顆石頭的顏色，若為黑色則該數為 1，否則為 0。

如果你的程式被判斷為 Wrong Answer，範例評分程式會輸出 Wrong Answer: MSG，其中 MSG 以及其代表的意思為以下列表的其中一個：

• S must be nonempty: query 函式傳入的 $S$ 為空。
• elements in S must be between 0 and n-1: query 函式傳入的 $S$ 內有不在 $0$ 至 $n-1$ 範圍內的數。
• duplicate elements in S: query 函式傳入的 $S$ 內有重複的數。
• Too many queries: query 的呼叫次數過多。
• invalid answer：回傳的陣列長度不是 $n$，或是回傳的陣列元素不是 0 或 1。

如果有多個原因，範例評分程式只會輸出任何一個。

另外請注意，範例評分程式並不會幫你檢查你回傳的任何數值是否是正確的。

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

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

IOICamp 2025 Day5 pK