P3777 [APIO2017] Koala's Game.

### Special Note **Notes for submitting this problem on Luogu (if different from the original statement, follow this section):** 1. When submitting, add the following function declaration in your program: ```cpp void playRound(int*,int*); ``` 2. At the beginning of the program, you do not need to, and should not, include the `koala.h` header file. 3. Only `C++` (including `C++`, `C++11`, `C++14`, `C++17`) submissions are supported.

Koala has invented a new game and invites you to play. At the start of the game, she places $N$ items on the table, numbered from $0$ to $N - 1$. Then, she secretly assigns each item an integer weight between $1$ and $N$, and no two items are assigned the same weight. The weight of item $i$ is $P_i$. She asks you to determine some properties of the sequence of weights $P=P_0,P_1,\dots,P_{N-1}$. To answer her questions, you may ask Koala to play several rounds. In each round, you receive $W$ blue stones, and Koala receives $W$ red stones. First, you may choose some items and place some (or all) of your stones next to these items. Koala observes your placement, and then similarly places some (or all) of her stones next to some items. If the number of red stones next to an item is strictly greater than the number of blue stones next to it, then Koala can obtain this item. When Koala places her stones, she will always choose a plan that maximizes the total weight of the items she obtains. If there are multiple such plans, she will choose one that obtains the maximum number of items. If there are still multiple plans, she may choose any of them. Koala is very lazy. If you play too many rounds with her, she will fall asleep. Your task is to determine the required properties of Koala’s sequence $P$ using as few rounds as possible. ### Task In this task, you need to implement $4$ functions: `minValue`, `maxValue`, `greaterValue`, and `allValues`. Each function requires you to determine a different property of the sequence $P$. We strongly recommend that you write your solution based on the template we provide. Note that even if you only want to get points for some subtasks, you must provide an implementation for all four functions (although some function bodies may be empty). Your program is not allowed to read from standard input, write to standard output, or interact with any files. In each function, parameter `N` is the number of items in the game, and parameter `W` is the number of stones that you and Koala have in each round. * `minValue(N, W)` --- This function should return the index $i$ of the item with the minimum weight, i.e. $P_i=1$. * `maxValue(N, W)` --- This function should return the index $i$ of the item with the maximum weight, i.e. $P_i=N$. * `greaterValue(N, W)` --- This function should compare the weights of item $0$ and item $1$, and return the index of the item with the larger weight. Specifically, if $P_0>P_1$, it should return $0$, otherwise it should return $1$. * `allValues(N, W, P)` --- This function should determine the entire permutation and store it into the given array $P$. Specifically, $P[i]$ should store the weight $P_i$ of item $i$ $(0 \leq i \leq N-1)$. In each test case, the interaction library will call one of these functions one or more times. Each function call represents a different task. Which function will be called, and the maximum number of calls, depend on the subtask (see below). You may assume that Koala fixes her sequence $P$ before each function call, and that the sequence will not change during a single function call. After one call ends, she may change her sequence before the next call. The four functions you implement can obtain information about Koala’s sequence by calling the function `playRound`. * `playRound(B, R)`: ask Koala to play one round. Array `B` describes how many blue stones you place next to each item. Specifically, for any $0 \leq i \leq N-1$, $B[i]$ blue stones will be placed next to item $i$. Each $B[i]$ must be a non-negative integer, and $B[0]+B[1]+\cdots +B[N-1]$ must not exceed $W$. The interaction library will store Koala’s response in the array `R` you provide. Specifically, for any $0 \leq i \leq N-1$, Koala will place $R[i]$ red stones next to item $i$. Each subtask has a limit on how many times you may call `playRound` within each game. Note that fewer calls may yield a higher score. (See below for the exact limits and scoring method.)

N/A

N/A

### Subtasks #### Sample testdata: $0$ points **Due to special reasons (setting $0$-point test cases is not supported), the sample will not be tested during judging.** * There are $5$ “sample testdata” test cases. In each test case, exactly one of the $4$ functions is called exactly once. See the “Samples” section below for details of each test case. * $N=6$ * $P=5,3,2,1,6,4$ In each game, you may call `playRound` at most $3200$ times. #### Subtask 1: $4$ points * In this subtask, the interaction library will only call `minValue`. In each test case, this function will be called at most $100$ times. * $N=100$ * $W=100$ * In each game, you may call `playRound` at most $2$ times. #### Subtask 2: $15$ points * In this subtask, the interaction library will only call `maxValue`. In each test case, this function will be called at most $100$ times. * $N=100$ * $W=100$ * In each game, you may call `playRound` at most $13$ times. * In this subtask, the score of a test case depends on the maximum number of times `playRound` is called in any game, denoted $C_{max}$. Specifically, your score is: - If $C_{max}\leq 4$, you get $15$ points. - If $5 \leq C_{max} \leq 13$, you get $7$ points. #### Subtask 3: $18$ points * In this subtask, the interaction library will only call `greaterValue`. In each test case, this function will be called at most $1100$ times. * $N=100$ * $W=100$ * In each game, you may call `playRound` at most $14$ times. * In this subtask, the score of a test case depends on the maximum number of times `playRound` is called in any game, denoted $C_{max}$. Specifically, your score is: - If $C_{max}\leq 3$, you get $18$ points. - If $C_{max}=4$, you get $14$ points. - If $C_{max}=5$, you get $11$ points. - If $6 \leq C_{max}\leq 14$, you get $5$ points. #### Subtask 4: $10$ points * In this subtask, the interaction library will only call `allValues`. In each test case, this function will be called exactly once. * $N=100$ * $W=200$ * You may call `playRound` at most $700$ times. #### Subtask 5: $53$ points * In this subtask, the interaction library will only call `allValues`. In each test case, this function will be called exactly once. * $N=100$ * $W=100$ * You may call `playRound` at most $3200$ times. * In this subtask, the score of a test case depends on the number of times `playRound` is called, denoted $C$. Specifically, your score is: - If $C \leq 100$, you get $53$ points. - If $101 \leq C \leq 3200$, you get $\lfloor 53-8 \log_2 (c/100) \rfloor$ points. Here, $\lfloor x \rfloor$ is the greatest integer not exceeding $x$. For example, if $C=3200$, your solution will get $13$ points. ### Scoring - As in traditional problems, your program’s time and memory usage must not exceed the limits. **The interaction library’s time and memory usage will also be counted in your total time and memory usage**. When estimating this part, you may assume that the interaction library used for judging has **the same functions** and a **similar implementation** as the sample interaction library we provide. - In a test case, if you pass an illegal array B when calling `playRound`, or if the total number of calls to `playRound` exceeds the limit, then the score for that test case is $0$. - In any game within a test case, if a function does not correctly answer the required property of Koala’s sequence, then the score for that test case is $0$. - Both Subtask 4 and Subtask 5 require you to implement `allValues`, but they pass different values of $W$ when calling it. You can use this difference in your implementation to distinguish between the two subtasks. You can refer to your language’s template for more detailed information. - During the contest, you may submit this problem at most 60 times, and there must be at least 2 minutes between two consecutive submissions. - **Your score for a subtask equals the lowest score among all test cases in that subtask.** ### How to test your program Compile with the following command in the terminal: ```bash g++ grader.cpp koala.cpp -o grader -g -Wall --std=c++11 ``` The sample interaction library will read input from standard input in the following format: The first line contains two integers $F,G$, where $F$ is the type of function called by the interaction library, and $G$ is the number of function calls. Then there are $G$ lines. Each line starts with two integers $N,W$, followed by $N$ integers $P_0,P_1,\ldots,P_{N-1}$. The function type corresponding to $F$ is shown in the following table: | $F$ | Function called | | ----------- | ----------- | | $1$ | `minValue` | | $2$ | `maxValue` | | $3$ | `greaterValue` | | $4$ | `allValues` | For each function call, the sample interaction library will output two lines to standard output. The first line is the number of times you called `playRound`. The second line is the result returned after the function call (for $F=4$, it outputs the array returned by `allValues`; for other cases, it outputs the return value of the function). ### Samples Consider the following permutation: | $i$ | 0 | 1 | 2 | 3 | 4 | 5 | | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | ----------- | | $P_i$ | 5 | 3 | 2 | 1 | 6 | 4 | The table below shows some example calls to `playRound` and valid feedback from the interaction library for each call (note that a single call to `playRound` may have multiple possible valid feedbacks). | $W$ | Call | Possible feedback from the interaction library | Explanation | | ----------- | ----------- | ----------- | ----------- | | 6 | `playRound([0,3,0,2,1,0],R)` | `R=[1,1,1,0,2,1]` | Koala obtains items $0,2,4,5$, with total weight $17$. This is one possible plan that maximizes the total weight. | | 6 | `playRound([1,2,3,1,2,0],R)` | Illegal call | You placed a total of $9$ stones, exceeding the limit $W$. | | 12 | `playRound([0,3,0,2,1,0],R)` | `R=[2,3,0,2,3,1]` | You do not have to use all $W$ stones, and Koala does not have to use all $W$ stones either. | | 6 | `playRound([0,1,0,0,1,0],R)` | `R=[1,0,1,1,2,1]` | If Koala has multiple plans that maximize the total weight of obtained items, she will choose the one that lets her obtain the most items. Therefore, `R=[1,2,0,0,2,1]` is not a legal return value. | Below are the expected return values for the sample testdata. Note that in the sample testdata, you may call `playRound` at most $3200$ times. | # | Function call by the interaction library | Expected return value | Explanation | | ----------- | ----------- | ----------- | ----------- | | 1 | `minValue(6,6)` | 3 | $P_3=1$ | | 2 | `maxValue(6,6)` | 4 | $P_4=6$ | | 3 | `greaterValue(6,6)` | 0 | $P_0=5,P_1=3$ | | 4 | `allValues(6,12,P)` | `P=[5,3,2,1,6,4]` | Note that `allValues` has no return value; it stores the correct result into $P$. | | 5 | `allValues(6,12,P)` | `P=[5,3,2,1,6,4]` | Same as above. | ### Additional Files The additional files include the sample input and output, the C++ sample interaction library, and the program template. We recommend that you implement your program based on the template. Translated by ChatGPT 5