ioicamp ioicamp-2026

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

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

你需要實作以下兩個函式：

void check_network(int N);

• 對於輸入的陣列大小 $N$，判斷排序網路 $P$ 的正確性。

bool is_sorting_correct(vector<int> A);

• 對於使用者的輸入陣列 $A$，回傳 $A$ 經過 aisort() 之後是否會被排好。
• 保證 $A$ 的長度為 $N$，且 $A$ 的所有數值皆相異。

你可以在 check_network() 的實作裡呼叫以下函式若干次：

vector<int> aisort(vector<int> A);

將陣列 $A$ 使用 AI 排序法。回傳的結果為 $A$ 經過排序的結果。注意，$A$ 的長度必須為 $N$，否則你會獲得 WA。

評測系統會用以下過程執行每一筆測試資料：

• 呼叫 check_network(N) 一次。
• 呼叫 is_sorting_correct() $Q$ 次，並檢查回傳值是否正確。

如果任意一個 is_sorting_correct() 的回傳值錯誤，你會獲得 WA，否則你的分數會依照下方 Scoring 的公式計算。

假設 $N = 4, k = 6$，一個可能被判斷為 Accepted 的範例互動狀況如下：

評測程式端	參賽者程式端
呼叫 check_network(4)。
	呼叫 aisort({3, 2, 4, 1})。
回傳 {1, 2, 3, 4}。
	呼叫 aisort({0, 0, 0, 0})。
回傳 {0, 0, 0, 0}。
	check_network() 函式 return。
呼叫 is_sorting_correct({1, 3, 4, 2})。
	回傳 true。

• $2 \leq N \leq 9$
• $1 \leq Q \leq 20000$
• $1 \leq k \leq 100$，$k$ 為排序網路的交換次數。

令 $C$ 為所有測資中，呼叫 aisort() 的最大次數。你的得分為

$$
\begin{cases}
100, & \text{ if } C \le 125 \\
\frac{100}{1 + \frac{1}{2}\log_2 \frac{C}{125}}, & \text{ if } C > 125
\end{cases}
$$

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

• 第一行輸入整數 $N$ $k$
• 接下來 $k$ 行每行有兩個整數 $x_i$ $y_i$，代表排序網路中的第 $i$ 次比較。
• 下一行輸入整數 $Q$
• 接下來 $Q$ 行每行有 $N$ 個整數 $A_1, A_2, \dots, A_N$，代表詢問的陣列 $A$。

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

如果你的程式被判斷為 Accepted，範例評分程式會輸出 Accepted: C，其中 C 為你的程式呼叫 aisort() 的次數。

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

• Invalid call to aisort: 呼叫 aisort() 時陣列 $A$ 的長度不等於 $N$。
• Cannot call aisort() inside is_sorting_correct().: 不能在回答詢問時呼叫 aisort()。
• On query X, Expected A, got B: 答案在第 $X$ 個詢問錯誤。評分程式只會輸出第一個錯誤的詢問。

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

請注意，範例評分程式的評測方法與實際評分程式不同，實際評測系統會用在 Implementation Details 欄位敘述的方法執行。

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

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