Background

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:

int compare_tastiness(std::vector<int> S1, std::vector<int> S2);

Problem Description

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:

#include "cake.h"

Contestants need to implement the following two functions in the submitted source file cake.cpp:

std::vector<int> 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.

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:

int compare_tastiness(std::vector<int> S1, std::vector<int> 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:

g++ grader.cpp cake.cpp -o cake -O2 -std=c++14 -static

Input Format

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.

40 20 5 3
19 7 20

Correct: found 19 in 4 compares
Correct: found 7 in 5 compares
Correct: found 20 in 5 compares
Correct. Max compare count is 5

Hint

Sample 1 Explanation

The interaction library will make the following call:

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:

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