ioicamp ioicamp-2024

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

你的程式需要在一開始使用前置處理器引入 lib0058.h，請注意在本地測試時你需要改為引入 reporter.h，詳細請參考範例實作。

你需要完成以下的函式：

std::vector<int> get_ranking(int N);

• 在一筆測試資料中，get_ranking 只會被呼叫剛好 $1$ 次。
• 引數 N 為題目中的參數 $N$。
• 回傳值必須為一個長度為 $N$ 的陣列，第 $i$ 項為名次第 $i$ 名的參賽者編號，即滿足 $r_j=i$ 的 $j$。

你可以呼叫以下函式：

int get_downvote(std::vector<int> g);

• 引數 g 必須為一個長度為 $N$ 的陣列，第 $i$ 項為你這次猜測第 $i$ 名的參賽者編號，即滿足 $g_j=i$ 的 $j$。
• 回傳值是一個整數，表示這次猜測所得到的負評數量。
• get_downvote 不得被呼叫超過 $Q=\mathbf{\text{200 000}}$ 次。

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

假設 $N=4,Q=\mathbf{\text{200 000}},r=$ {0, 1, 3, 2}，一個被判斷為 Accepted 的範例互動狀況如下：

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

在第一次查詢中，僅有編號為 $3$ 的參賽者會發出抱怨，因為他的實際排名為 $2$ 卻被猜測為 $3$。在第二次查詢中，所有人都在正確的排名上，所以沒有人會抱怨，因此回傳 $0$。

• $1\le N\le 500$
• $Q=\mathbf{\text{200 000}}$
• 排名皆相異。
• 排名 $r$ 不會隨著互動過程而改變。

假設你呼叫 get_downvote 的次數為 $q$，你的得分 $S$ 由下列方式計算：

• 如果 $q\le 4000$， $$S=100$$
• 如果 $4000<q\le 4200$，
  $$S=70+30\times {\left(\frac{4200-q}{200}\right)}^2$$
• 如果 $4200<q\le 5000$，
  $$S=25+45\times \left(\frac{5000-q}{800}\right)$$
• 如果 $5000<q\le 20000$，
  $$S=10+15\times \left(\frac{20000-q}{15000}\right)$$
• 如果 $20000<q\le 200000$，
  $$S=10$$

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

• line 1: $N$
  
• line 2: $r_0$ $r_1$ $\cdots$ $r_{N-1}$
  

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

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

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

• invalid guess：猜測的排名不合法，也就是說，g 的長度不是 $N$、g 當中有相同的參賽者編號或者 g 當中的參賽者編號超出 $0$ 至 $N-1$ 的範圍。
• invalid answer：回傳的排名不合法，也就是說，回傳的排名長度不是 $N$、回傳的排名當中有相同的參賽者編號或者回傳的排名當中的參賽者編號超出 $0$ 至 $N-1$ 的範圍。
• too many queries：猜測的次數超過限制。
• not correct：回傳的排名不正確。

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

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

• 如果你的系統是 Linux，你可以直接執行 compile.sh 編譯你的程式，編譯結果會是 reporter，請直接用命令列執行該檔案。
• 如果你的系統是 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 2024 Day6 pK