P16434 [APIO 2026 中国赛区] 蛋糕
题目背景
提交时请选择高于 C++17 的语法标准，不要引入头文件 `cake.h`，并把下列代码复制到程序开头：
```cpp
int compare_tastiness(std::vector S1, std::vector S2);
```
题目描述
Lavi 是一位很喜欢吃蛋糕的小星使。她认为每块蛋糕的美味度都可以定义为一个正整数。
有一天，她的好朋友 Sally 买来了一块蛋糕。这块蛋糕的美味度是一个不大于 $W$ 的正整数 $d$，但 Lavi 此时只知道 $W$ 的值。现在 Lavi 想要求出 $d$ 的值。
运用星使的力量，Lavi 可以制作出至多 $N$ 块美味度分别不超过 $W + 200$ 的蛋糕并告知 Sally；然后 Sally 会偷偷地将买来的那块蛋糕混进这些蛋糕中，最后 Sally 会将这些蛋糕 **按美味度升序排序**。由于这些不同美味度的蛋糕在外表上没有任何区别，所以 Lavi 暂时不能分辨出哪块蛋糕是 Sally 买来的。不过 Sally 有很强的记忆力，因此她清晰地记得排序后每块蛋糕的美味度。
将蛋糕排序后，Lavi 可以多次向 Sally 进行以下询问：
* Lavi 选出若干块蛋糕，将它们分为不相交的两组，然后 Sally 会告知 Lavi 两组蛋糕美味度之和的大小关系。
形式化地，假设 Lavi 制作了 $m$ 块蛋糕，记 $a_0, a_1, a_2, \dots, a_m$ 为将 Sally 买来的蛋糕混入并排序后每块蛋糕的美味度，那么 Lavi 每次需要给出两个非空下标集合 $S_1, S_2$，满足 $S_1, S_2 \subseteq \{0, 1, 2, \dots, m\}$ 且 $S_1 \cap S_2 = \varnothing$。Sally 会告知 Lavi $\sum_{i \in S_1} a_i$ 与 $\sum_{i \in S_2} a_i$ 的大小关系。
现在 Lavi 需要你的帮助！但她提醒你，询问次数过多会对 Sally 的记忆力提出很大的考验，因此 Sally 对询问次数做出了一定限制。具体地，Sally 会在 Lavi 制作蛋糕前给出一个正整数 $K$，如果 Lavi 作出了多于 $K$ 次询问，那么你获得的分数会随询问次数增加而减少。
请协助 Lavi 决定制作蛋糕的策略以及随后的询问策略。
### 【实现细节】
选手不需要，也不应该实现 main 函数。
选手需要确保提交的程序包含头文件 cake.h，即在程序开头加入以下代码：
```cpp
#include "cake.h"
```
选手需要在提交的程序源文件 cake.cpp 中实现以下两个函数：
```cpp
std::vector bake_cakes(int N, int W, int K);
```
* $N$ 表示 Lavi 最多可制作的蛋糕数。
* $W$ 表示 Sally 买来的蛋糕的美味度上界。
* $K$ 表示询问次数阈值。
* 该函数需要返回一个正整数数组 $c$，表示 Lavi 制作出每块蛋糕的美味度，其中：
* $c$ 的长度 $m$ 不能超过 $N$；
* 对于所有 $0 \le i \le m - 1$，均有 $1 \le c_i \le W + 200$。
* 对于每个测试点，该函数会被交互库调用恰好一次，且在所有 `find_tastiness` 函数调用之前。
```cpp
int find_tastiness(int m, int W, int K);
```
* $m$ 表示 Lavi 制作出的蛋糕数，也就是说，包含 Sally 买来的蛋糕后实际蛋糕数为 $m + 1$。
* $W$ 表示 Sally 买来的蛋糕的美味度上界。
* $K$ 表示询问次数阈值。
* 该函数需要返回一个正整数 $d$，表示 Lavi 求出的 Sally 买来的蛋糕的美味度。
* 对于每个测试点，该函数可能会被交互库调用多次，每次调用之间是独立的。
在该函数中，你可以调用以下函数：
```cpp
int compare_tastiness(std::vector S1, std::vector S2);
```
* $S_1, S_2$ 分别为两组蛋糕的下标集合，你需要满足 $S_1, S_2$ 非空且其中的元素互不相同，即 $S_1, S_2 \subseteq \{0, 1, 2, \dots, m\}$ 且 $S_1 \cap S_2 = \varnothing$。
* 该函数会返回一个整数 $r \in \{-1, 0, 1\}$ 代表 $v_1 = \sum_{i \in S_1} a_i$ 与 $v_2 = \sum_{i \in S_2} a_i$ 的大小关系，其中 $r = -1$ 代表 $v_1 < v_2$，$r = 0$ 代表 $v_1 = v_2$，$r = 1$ 代表 $v_1 > v_2$。
* 在一次 find_tastiness 的调用中，你可以调用该函数至多 $100$ 次。
评测程序不是适应性的，Sally 买来的蛋糕的美味度 $d$ 在每次 find_tastiness 的调用前就已经确定。
### 【测试程序方式】
选手可以在本题目录下使用如下命令编译得到可执行程序：
```bash
g++ grader.cpp cake.cpp -o cake -O2 -std=c++14 -static
```
输入格式
对于编译得到的可执行程序：
* 可执行文件将从标准输入读入以下格式的数据：
* 输入的第一行包含四个正整数 $N, W, K, T$。
* 输入的第二行包含 $T$ 个正整数 $d_1, d_2, \dots, d_T$，分别表示每次调用 `find_tastiness` 时 Sally 买来的蛋糕的美味度。
* 可以通过在运行时启用 `-v` 或 `--verbose` 参数来输出更详细的交互流程。在未启用该参数的情况下，程序会在每次调用完 `find_tastiness` 后输出返回值的正确性以及 `compare_tastiness` 的调用次数，并在所有调用完成后输出 `compare_tastiness` 的最大调用次数。启用 `-v` 或 `--verbose` 参数后，程序将会额外输出以下内容：
* 调用 `bake_cakes` 后函数的返回值。
* 每次 `compare_tastiness` 被调用时传递的参数，比较信息以及比较结果。
输出格式
无
说明/提示
### 【样例 1 解释】
交互库将进行以下调用：
```cpp
bake_cakes(40, 20, 5);
```
Lavi 可以制作至多 $40$ 个蛋糕，Sally 买来的蛋糕的美味度上界为 $20$，询问次数阈值为 $5$。
一种可能的返回数组为 $[12, 1, 22, 9, 19, 1, 12, 12, 25]$。
接下来交互库将进行三次以下调用：
```cpp
find_tastiness(9, 20, 5);
```
其中每次调用时 Sally 买来的蛋糕的美味度分别为 $19, 7, 20$。
* Sally 买来的蛋糕的美味度为 $19$ 时，所有蛋糕排序后美味度分别为 $[1, 1, 9, 12, 12, 12, 19, 19, 22, 25]$。此时，
* 若调用 `compare_tastiness([0, 2, 4], [1, 3, 5])`，则 $S_1$ 中蛋糕美味度之和为 $1+9+12=22$，$S_2$ 中蛋糕美味度之和为 $1+12+12=25$，因此该函数会返回 $-1$；
* 若调用 `compare_tastiness([8, 2, 6], [5, 0, 9])`，则 $S_1$ 中蛋糕美味度之和为 $22+9+19=50$，$S_2$ 中蛋糕美味度之和为 $12+1+25=38$，因此该函数会返回 $1$；
* 若调用 `compare_tastiness([0, 4, 7], [1, 3, 6])`，则 $S_1$ 中蛋糕美味度之和为 $1+12+19=32$，$S_2$ 中蛋糕美味度之和为 $1+12+19=32$，因此该函数会返回 $0$。
* Sally 买来的蛋糕的美味度为 $7$ 时，所有蛋糕排序后美味度分别为 $[1, 1, 7, 9, 12, 12, 12, 19, 22, 25]$。此时，
* 若调用 `compare_tastiness([0, 1, 3], [6])`，则 $S_1$ 中蛋糕美味度之和为 $1+1+9=11$，$S_2$ 中蛋糕美味度之和为 $19$，因此该函数会返回 $-1$。
### 【数据范围】
对于所有测试数据，均有：
- $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$；
- 对于所有 $1 \le i \le T$，均有 $1 \le d_i \le W$。
::cute-table{tuack}
| 测试点编号 | 分值 | $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$ | ^ |
### 【评分方式】
在任意测试用例中，如果 `bake_cakes` 的返回值不符合实现细节中的约束条件，或者 `compare_tastiness` 的调用不符合实现细节中的约束条件，或者 `find_tastiness` 的返回值不正确，则该子任务得 $0$ 分。
对于每个测试点，记 $Q$ 为该测试点所有 `find_tastiness` 的调用中，`compare_tastiness` 调用次数的最大值，则程序得到的分数将按照以下方式计算：
* 在测试点 $1, 2$ 中，若 $Q \le K$，则得分为该测试点的分值，否则得分为 $0$；
* 在测试点 $3$ 中，得分为 $\max(30 - 3 \cdot \max(Q - K, 0), 0)$；
* 在测试点 $4$ 中，得分为 $\max(55 - 11 \cdot \max(Q - K, 0), 0)$。