P6837 [IOI 2020] Counting Mushrooms

Do not `#include "mushrooms.h"`. You need to add the following content at the top of the file, and **submit using $\text{\textcolor{red}{C++\,23}}$**: ```cpp line-numbers #include int use_machine(std::vector x); ```

Mushroom expert Andrew is studying local mushrooms in Singapore. As part of the study, Andrew collected $n$ mushrooms, numbered from $0$ to $n-1$. Each mushroom belongs to one of two species, called $A$ or $B$. Andrew knows that **mushroom $0$ belongs to species $A$**, but since the two species look very similar, he does not know whether mushrooms $1$ to $n-1$ are $A$ or $B$. Fortunately, Andrew has a machine in his lab that can help. To use the machine, you put two or more mushrooms into the machine and arrange them in a line (in any order), then turn on the machine. The machine will compute the number of **adjacent** pairs of mushrooms that are not of the same species. For example, if you put mushrooms of species $\left[A, B, B, A\right]$ (in this order) into the machine, the result should be $2$. However, because operating the machine is very expensive, it can only be used a limited number of times. Moreover, across all uses of the machine, the total number of mushrooms placed into the machine cannot exceed $10^5$. Use this machine to help Andrew count how many mushrooms of species $A$ he collected. #### Implementation details You need to implement the following function: ```cpp line-numbers int count_mushrooms(int n) ``` - `n`: the number of mushrooms Andrew collected. - This function will be called exactly once, and it should return the number of mushrooms of species $A$. The above function may call the following function: ```cpp line-numbers int use_machine(vector x) ``` - `x`: an array of length between $2$ and $n$ (inclusive), giving in order the indices of the mushrooms placed into the machine. - The elements of `x` must be **distinct** integers between $0$ and $n-1$ (inclusive). - Suppose the length of `x` is $d$. Then this function returns the number of indices $j$ such that $0 \le j \le d-2$ and $x[j]$ and $x[j+1]$ belong to different species. - This function can be called at most $2 \times 10^4$ times. - Across all calls to `use_machine`, the sum of the lengths of all arrays $x$ passed to `use_machine` must not exceed $10^5$.

N/A

N/A

#### Sample explanation #### Example 1 Consider the following scenario: there are $3$ mushrooms, with species in order $\left[A,B,B\right]$. The function `count_mushrooms` is called in the following way: ```cpp line-numbers count_mushrooms(3) ``` This function can call `use_machine([0, 1, 2])`, which in this scenario returns $1$. The function then calls `use_machine([2, 1])`, which returns $0$. At this point, there is enough information to conclude that there is only $1$ mushroom of species $A$. Therefore, `count_mushrooms` should return $1$. #### Example 2 Consider the following example: there are $4$ mushrooms, with species in order $\left[A,B,A,A\right]$. The function `count_mushrooms` is called as follows: ```cpp line-numbers count_mushrooms(4) ``` This function can call `use_machine([0, 2, 1, 3])`, which returns $2$. It then calls `use_machine([1,2])`, which returns $1$. At this point, there is enough information to conclude that there are $3$ mushrooms of species $A$. Therefore, `count_mushrooms` should return $3$. #### Constraints - $2 \le n \le 2 \times 10^4$ #### Scoring For all test cases, if your calls to `use_machine` do not satisfy the requirements described above, or if the return value of `count_mushrooms` is not correct, your score will be $0$. Otherwise, let $Q$ be the maximum number of calls to `use_machine` among all test cases. Then your score will be computed according to the following table: |Condition|Score| |:-:|:-:| |$2 \times 10^4 \le Q$|$0$| |$10010 < Q \le 2 \times 10^4$|$10$| |$904 < Q \le 10010$|$25$| |$226 < Q \le 904$|$\dfrac{226}{Q} \cdot 100$| |$Q \le 226$|$100$| On some test cases, the behavior of the grader is adaptive. That is, in these test cases, the grader does not have a fixed sequence of mushroom species. Instead, the answers given by the grader may depend on previous calls to `use_machine`. However, it is guaranteed that the answers given by the grader satisfy the following: after each interaction, there exists at least one sequence of mushroom species that is consistent with all answers given so far. #### Example grader The example grader reads an integer array $s$, which gives the species of the mushrooms. For all $0 \le i \le n-1$, $s[i]=0$ means mushroom $i$ is of species $A$, and $s[i]=1$ means mushroom $i$ is of species $B$. The example grader reads input in the following format: Line $1$: $n$ \ Line $2$: $s[0]\ s[1]\ \ldots\ s[n-1]$ The output of the example grader is in the following format: Line $1$: the return value of `count_mushrooms`. \ Line $2$: the number of calls to `use_machine`. Note that the example grader is not adaptive. Translated by ChatGPT 5