[IOI2020] 数蘑菇

研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。 作为研究的一部分，安德鲁采集了 $n$ 个蘑菇，编号为 $0$ 到 $n-1$。每个蘑菇均为两种蘑菇种类之⼀，称为 $A$ 或 $B$。 安德鲁知道 **蘑菇 $0$ 属于种类 $A$**, 但是由于这两种蘑菇看起来很相似，他不知道蘑菇 $1$ 到 $n-1$ 属于哪一种。 幸运的是，安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时，需要将两个或者多个蘑菇放到机器里，并摆成一排（以任意顺序），然后打开机器。接下来，这台机器会计算所有不属于同一种类的 **相邻** 蘑菇对的个数。例如，如果你把种类为 $[A,B,B,A]$ 的蘑菇（按照这个顺序）放到机器中，结果应该是 $2$。 但是，因为机器操作非常昂贵，机器只能使用有限的次数。此外，在机器的所有使用中，放置到机器中的蘑菇总数不能超过 $10^5$。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 $A$ 的蘑菇。 #### 实现细节 你需要实现以下函数： ```cpp int count_mushrooms(int n) ``` - $n$: 安德鲁采集到的蘑菇数量。 - 该函数应该被调用恰好一次，而且要返回种类为 $A$ 的蘑菇的个数。 以上函数可以调用以下函数： ```cpp int use_machine(int[] x) ``` - $x$: 一个长度介于 $2$ 和 $n$ 的数组（包括 $2$ 和 $n$)，按顺序给出放在机器中的蘑菇的编号。 - $x$ 的元素必须是在 $0$ 到 $n-1$ 之间（包括 $0$ 和 $n-1$) **互不相同** 的整数。 - 假设数组 $x$ 的长度为 $d$。那么，此函数返回不同的下标 $j$ 的个数，满足 $0 \le j \le d-2$ 并且 $x[j]$ 和 $x[j+1]$ 属于不同种类。 - 该函数最多可以被调用 $2 \times 10^4$ 次。 - 在对函数 `use_machine` 的所有调用中，所有被传到该函数 `use_machine` 的 $x$ 的总长度不能超过 $10^5$。

#### 样例说明 #### 例 1 考虑以下场景：有 $3$ 个蘑菇，种类依次为 $[A,B,B]$。函数 `count_mushrooms` 用以下方式调用 ```cpp count_mushrooms(3) ``` 该函数可以调用 `use_machine([0, 1, 2])`，在该场景下调用返回 $1$。 函数接着调用 `use_machine([2, 1])`，该调用返回 $0$。 此时，已经有足够的信息来推出只有 $1$ 个 $A$ 类蘑菇。所以，函数 `count_mushrooms` 应该返回 $1$。 #### 例 2 考虑一个例子：有 $4$ 个蘑菇，种类依次为 $[A,B,A,A]$。函数 `count_mushrooms` 被调用如下： ```cpp count_mushrooms(4) ``` 该函数可以调用 `use_machine([0, 2, 1, 3])`，该调用返回 $2$。接着调用 `use_machine([1,2])`，该调用返回 $1$。 此时，已有足够的信息推出：有 $3$ 个 $A$ 类蘑菇。因此，函数 `count_mushrooms` 应该返回 $3$。 #### 约束条件 - $2 \le n \le 2 \times 10^4$ #### 计分 在所有测试用例中，如果对函数 `use_machine` 的调用不符合上面所述的要求，或者 `count_mushrooms` 的返回值不正确，你的解答得分将为 $0$。否则，令 $Q$ 为所有测试样例中对函数 `use_machine` 的最大调用次数。那么，得分将按照以下表格进行计算： |条件|得分| |:-:|:-:| |$2 \times 10^4 \le Q$|$0$| |$10010 < Q \le 2 \times 10^4$|$10$| |$904 < Q \le 10010$|$25$| |$226 < Q \le 904$|$\frac{226}{Q} \cdot 100$| |$Q \le 226$|$100$| 在有些测试用例上，评测程序的行为是自适应的。也就是说，在这些测试用例中，评测程序并没有一个固定的蘑菇种类序列。相反，评测程序中所给出的回答可能依赖于此前对 `use_machine` 的调用。 但是可以保证，评测程序中所给出的回答满足：在每次交互之后，至少存在一个蘑菇种类序列，它能够与当前所给出过的所有回答都相符。 #### 评测程序示例 评测程序示例读入一个整数数组 $s$，该数组给出了蘑菇的种类。对于所有 $0 \le i \le n-1$，$s[i]=0$ 表示蘑菇 $i$ 的种类是 $A$，$s[i]=1$ 表示蘑菇 $i$ 的种类是 $B$。评测程序示例读取如下格式的输入数据： 第 $1$ 行: $n$ 第 $2$ 行: $s[0]\ s[1]\ \ldots\ s[n-1]$ 评测程序示例的输出为如下格式： 第 $1$ 行: `count_mushrooms` 的返回值。 第 $2$ 行: 调用 `use_machine` 的次数。 注意评测程序示例不是自适应的。