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