P16434 [APIO 2026 China Region] Cake

When submitting, please choose a language standard higher than C++17, do not include the header `cake.h`, and copy the following code to the beginning of your program: ```cpp int compare_tastiness(std::vector S1, std::vector S2); ```

Lavi is a little star messenger who really likes eating cake. She believes that the tastiness of each cake can be defined as a positive integer. One day, her good friend Sally bought a cake. The tastiness of this cake is a positive integer $d$ not greater than $W$, but at this moment Lavi only knows the value of $W$. Now Lavi wants to determine the value of $d$. Using the power of a star messenger, Lavi can make at most $N$ cakes, each with tastiness not exceeding $W + 200$, and tell Sally their tastiness values. Then Sally will secretly mix the bought cake into these cakes, and finally Sally will **sort all these cakes in non-decreasing order of tastiness**. Since cakes of different tastiness look exactly the same, Lavi cannot tell which one is the cake Sally bought. However, Sally has a very strong memory, so she clearly remembers the tastiness of every cake after sorting. After sorting, Lavi can ask Sally the following query multiple times: - Lavi chooses some cakes, splits them into two disjoint groups, and then Sally tells Lavi the comparison result between the sums of tastiness of the two groups. Formally, suppose Lavi made $m$ cakes. Let $a_0, a_1, a_2, \dots, a_m$ be the tastiness values of all cakes after mixing in Sally’s bought cake and sorting. Each time, Lavi needs to provide two non-empty index sets $S_1, S_2$, where $S_1, S_2 \subseteq \{0, 1, 2, \dots, m\}$ and $S_1 \cap S_2 = \varnothing$. Sally will tell Lavi the comparison result between $\sum_{i \in S_1} a_i$ and $\sum_{i \in S_2} a_i$. Now Lavi needs your help. But she reminds you that asking too many queries will put a big burden on Sally’s memory, so Sally sets a limit on the number of queries. Specifically, before Lavi makes cakes, Sally will give a positive integer $K$. If Lavi makes more than $K$ queries, your score will decrease as the number of queries increases. Please help Lavi decide how to bake the cakes and how to ask queries afterwards. ### Implementation Details Contestants do not need to, and should not, implement the `main` function. Contestants need to ensure that the submitted program includes the header file `cake.h`, i.e., add the following code at the beginning of the program: ```cpp #include "cake.h" ``` Contestants need to implement the following two functions in the submitted source file `cake.cpp`: ```cpp std::vector bake_cakes(int N, int W, int K); ``` - $N$ is the maximum number of cakes Lavi can bake. - $W$ is the upper bound of the tastiness of Sally’s bought cake. - $K$ is the query threshold. - This function should return a positive integer array $c$, representing the tastiness values of the cakes baked by Lavi, where: - the length $m$ of $c$ must not exceed $N$; - for all $0 \le i \le m - 1$, we have $1 \le c_i \le W + 200$. - For each test case, this function will be called by the interaction library exactly once, and it will be called before all calls to `find_tastiness`. ```cpp int find_tastiness(int m, int W, int K); ``` - $m$ is the number of cakes baked by Lavi, so the actual number of cakes after including Sally’s bought cake is $m + 1$. - $W$ is the upper bound of the tastiness of Sally’s bought cake. - $K$ is the query threshold. - This function should return a positive integer $d$, the tastiness of the cake bought by Sally as determined by Lavi. - For each test case, this function may be called multiple times by the interaction library, and each call is independent. In this function, you may call the following function: ```cpp int compare_tastiness(std::vector S1, std::vector S2); ``` - $S_1, S_2$ are the index sets of the two groups of cakes. You must ensure that $S_1, S_2$ are non-empty and all elements are distinct, i.e., $S_1, S_2 \subseteq \{0, 1, 2, \dots, m\}$ and $S_1 \cap S_2 = \varnothing$. - This function returns an integer $r \in \{-1, 0, 1\}$ representing the comparison result between $v_1 = \sum_{i \in S_1} a_i$ and $v_2 = \sum_{i \in S_2} a_i$, where $r = -1$ means $v_1 < v_2$, $r = 0$ means $v_1 = v_2$, and $r = 1$ means $v_1 > v_2$. - Within one call to `find_tastiness`, you may call this function at most $100$ times. The judge is not adaptive. The tastiness $d$ of Sally’s bought cake is already fixed before each call to `find_tastiness`. ### Testing Program Usage In the directory of this problem, contestants can compile into an executable using the following command: ```bash g++ grader.cpp cake.cpp -o cake -O2 -std=c++14 -static ```

For the compiled executable: - The executable will read input data from standard input in the following format: - The first line contains four positive integers $N, W, K, T$. - The second line contains $T$ positive integers $d_1, d_2, \dots, d_T$, representing the tastiness of the cake bought by Sally for each call to `find_tastiness`. - You can enable the `-v` or `--verbose` option at runtime to print a more detailed interaction process. If this option is not enabled, the program will output, after each call to `find_tastiness`, whether the returned value is correct and the number of calls to `compare_tastiness`, and after all calls are finished, it will output the maximum number of calls to `compare_tastiness`. If `-v` or `--verbose` is enabled, the program will additionally output: - the return value of `bake_cakes`; - for each call to `compare_tastiness`, the passed parameters, the compared information, and the comparison result.

N/A

### Sample 1 Explanation The interaction library will make the following call: ```cpp bake_cakes(40, 20, 5); ``` Lavi can bake at most $40$ cakes, the upper bound of the tastiness of Sally’s bought cake is $20$, and the query threshold is $5$. One possible returned array is $[12, 1, 22, 9, 19, 1, 12, 12, 25]$. Next, the interaction library will make the following call three times: ```cpp find_tastiness(9, 20, 5); ``` In these three calls, the tastiness of Sally’s bought cake is $19, 7, 20$, respectively. - When the tastiness of Sally’s bought cake is $19$, after sorting, the tastiness values of all cakes are $[1, 1, 9, 12, 12, 12, 19, 19, 22, 25]$. At this time, - if you call `compare_tastiness([0, 2, 4], [1, 3, 5])`, then the sum of tastiness in $S_1$ is $1+9+12=22$, the sum of tastiness in $S_2$ is $1+12+12=25$, so the function returns $-1$; - if you call `compare_tastiness([8, 2, 6], [5, 0, 9])`, then the sum of tastiness in $S_1$ is $22+9+19=50$, the sum of tastiness in $S_2$ is $12+1+25=38$, so the function returns $1$; - if you call `compare_tastiness([0, 4, 7], [1, 3, 6])`, then the sum of tastiness in $S_1$ is $1+12+19=32$, the sum of tastiness in $S_2$ is $1+12+19=32$, so the function returns $0$. - When the tastiness of Sally’s bought cake is $7$, after sorting, the tastiness values of all cakes are $[1, 1, 7, 9, 12, 12, 12, 19, 22, 25]$. At this time, - if you call `compare_tastiness([0, 1, 3], [6])`, then the sum of tastiness in $S_1$ is $1+1+9=11$, the sum of tastiness in $S_2$ is $19$, so the function returns $-1$. ### Constraints For all testdata: - $1 \le N \le 3 \times 10^3$, $1 \le W \le 10^9$, $1 \le K \le 100$, $1 \le T \le 2 \times 10^3$. - For all $1 \le i \le T$, $1 \le d_i \le W$. ::cute-table{tuack} | Test Point ID | Score | $N =$ | $W =$ | $K =$ | $T \leq$ | | :---: | :---: | :---: | :---: | :---: | :---: | | $1$ | $7$ | $3\,000$ | $10^2$ | $10^2$ | $10^2$ | | $2$ | $8$ | $3$ | $3$ | $1$ | $3$ | | $3$ | $30$ | $40$ | $10^9$ | $30$ | $2,000$ | | $4$ | $55$ | $3\,000$ | $2\,000$ | $7$ | ^ | ### Scoring For any test case, if the return value of `bake_cakes` does not satisfy the constraints in the implementation details, or the calls to `compare_tastiness` do not satisfy the constraints in the implementation details, or the return value of `find_tastiness` is incorrect, then this subtask scores $0$ points. For each test point, let $Q$ be the maximum number of calls to `compare_tastiness` among all calls to `find_tastiness` in that test point. The score of the program is computed as follows: - In test points $1, 2$, if $Q \le K$, the score equals the full score of that test point; otherwise, the score is $0$. - In test point $3$, the score is $\max(30 - 3 \cdot \max(Q - K, 0), 0)$. - In test point $4$, the score is $\max(55 - 11 \cdot \max(Q - K, 0), 0)$. Translated by ChatGPT 5