ioicamp ioicamp-2026

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

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

你需要完成以下函式：

std::pair<std::vector<int>, std::vector<int>> get_city_information(int N, int C);

• 在一次程式執行時，get_city_information 會被呼叫若干次，每次呼叫都是不同且獨立的測試資料，若使用全域變數，有需要的話務必記得重置。
• 引數 N 為水果古城中塔的數量 $N$。
• 引數 C 為水果古城中塔的最高可能高度。
• 回傳值必須為一個 std::pair，第一項為長度為 $N-1$ 的陣列 $p_1,p_2,\dots,p_{N-1}$，第二項為長度為 $N-1$ 的陣列 $d_1,\dots,d_{N-1}$。注意第二個陣列中不需要包含 $d_0$。

你可以呼叫以下函式：

std::vector<int> count_lower_energy(const std::vector<long long> &t);

• 引數 t 必須為一個長度為 $N$ 的陣列，且每個元素都在 $[-10^ {18}, 10^ {18}]$ 以內。
• 回傳值是一個陣列 $c_0,c_1,\dots,c_{N-1}$。
• 在一次執行 get_city_information 的過程中，count_lower_energy 不得被呼叫超過 $\textbf{700}$ 次。
• 此函數的執行時間會被計入你的執行時間中。此函數的實作在實際的評分程式中，與範例評分程式中的相同。

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

假設 $N = 5, p_i=i-1, h=[2,6,7,5,1]$，一個被判斷為 Accepted 的範例互動狀況如下：

評測程式端	參賽者程式端
呼叫 get_city_information(5, 1000000)。
	呼叫 count_lower_energy({1, 0, -3, 0, 4})
回傳 {0, 2, 0, 1, 1}。
	呼叫 count_lower_energy({6, 0, 0, 0, 0})
回傳 {1, 0, 2, 1, 0}。
	呼叫 count_lower_energy({0, 1, 0, 0, 4})
回傳 {0, 1, 2, 0, 1}。
	回傳 {{0, 1, 2, 3}, {4, 5, 3, -1}}。

• $2 \leq N \leq 10^ 5$
• 所有 $N$ 的總和不超過 $10^ 5$
• $1 \leq h_i \leq C \leq 10^ 6$
• $p_i < i$

假設你在所有測試資料中，單筆測試資料的 count_lower_energy 呼叫次數為 $q$，若 $q$ 超過 700，你會獲得 Wrong Answer 並得到 0 分。除了最後一筆子任務，只要 $q \leq 700$ 即可獲得滿分；對於最後一筆子任務，令 $S$ 為該子任務的滿分，你的得分會按照以下方式計算：

• 如果 $q \leq 38$，你會得到 $S$ 分。
• 否則，你的得分是 $$ S \times \max\left(1+\log_{7.5}\frac{18}{q-20}, \frac{1}{5.5}\right) $$

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

首行輸入一個 $T$，代表測試資料的數量，接著每一筆測試資料都以下列格式輸入：

• line $1$: $N$ $C$
• line $2$: $p_1$ $p_2$ $\dots$ $p_{N-1}$
• line $3$: $h_0$ $h_1$ $\dots$ $h_{N-1}$

對於每一筆測試資料，範例評分程式以下列方式輸出：

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

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

• too many queries：count_lower_energy 的呼叫次數超過 $700$。
• invalid call：count_lower_energy 函式的呼叫不合法，也就是說，t 不是一個長度為 $N$ 的陣列，或有元素不在 $[-10^ {18}, 10^ {18}]$ 以內。
• incorrect answer：get_city_information 回傳的答案不正確。

如果有多個原因，範例評分程式只會輸出任何一個。一旦被判定為 Wrong Answer，程式就會被終止。

範例評分程式提供了一個可以通過編譯的實作，但上傳後不會得到任何分數。

另外，請注意在程式執行時 get_city_information 可能會被呼叫超過一次，建議盡量只使用區域變數。若使用了全域變數，也請務必記得重設。

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

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