#3368. 「IOI2020」数蘑菇

内存限制:1024 MiB 时间限制:2000 ms 题目类型:交互
上传者: PinkRabbit

题目描述

注意:在 LibreOJ 上,由于语言限制,目前只支持以下语言的提交:

  • C++ 11
  • C++ 11 (Clang)
  • C++ 11 (NOI)
  • C++ 17
  • C++ 17 (Clang)

研究蘑菇的专家安德鲁在研究新加坡的本地蘑菇。作为研究的一部分,安德鲁采集了 n 个蘑菇,编号为 0 n-1 。每个蘑菇均为两种蘑菇种类之一,称为 A 或 B。

安德鲁知道蘑菇 0 属于种类 A ,但是由于这两种蘑菇看起来很相似,他不知道蘑菇 1 n-1 属于哪一种。

幸运的是,安德鲁的实验室里有一台机器可以帮助他。在使用这台机器时,需要将两个或者多个蘑菇放到机器里,并摆成一排(以任意顺序),然后打开机器。接下来,这台机器会计算所有不属于同一种类的相邻蘑菇对的个数。例如,如果你把种类为 [A,B,B,A] 的蘑菇(按照这个顺序)放到机器中,结果应该是 2

但是,因为机器操作非常昂贵,机器只能使用有限的次数。此外,在机器的所有使用中,放置到机器中的蘑菇总数不能超过 10^5 。请使用这台机器帮助安德鲁来数一数他采集了多少个种类为 A 的蘑菇。

实现细节

你需要实现以下函数:

int count_mushrooms(int n)
  • n :安德鲁采集到的蘑菇数量。
  • 该函数应该被调用恰好一次,而且要返回种类为 A 的蘑菇的个数。

以上函数可以调用以下函数:

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

评测程序示例

评测程序示例读入一个整数数组 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 的次数。

注意评测程序示例不是自适应的。

样例

样例输入 1

3
0 1 1

样例说明 1

考虑以下场景:有 3 个蘑菇,种类依次为 [A,B,B] 。函数 count_mushrooms 用以下方式调用:

count_mushrooms(3)

该函数可以调用 use_machine([0, 1, 2]),在该场景下调用返回 1 。函数接着调用 use_machine([2, 1]),该调用返回 0

此时,已经有足够的信息来推出只有 1 个 A 类蘑菇。所以,函数 count_mushrooms 应该返回 1

样例输入 2

4
0 1 0 0

样例说明 2

考虑一个例子:有 4 个蘑菇,种类依次为 [A,B,A,A] 。 函数 count_mushrooms 被调用如下:

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 的最大调用次数。那么,得分将按照以下表格进行计算:

条件 得分
20\ 000<Q 0
10\ 010<Q\le 20\ 000 10
904<Q\le 10\ 010 25
226<Q\le 904 \frac{226}{Q}\cdot 100
Q\le 226 100

在有些测试用例上,评测程序的行为是自适应的。也就是说,在这些测试用例中,评测程序并没有一个固定的蘑菇种类序列。相反,评测程序中所给出的回答可能依赖于此前对 use_machine 的调用。但是可以保证,评测程序中所给出的回答满足:在每次交互之后,至少存在一个蘑菇种类序列,它能够与当前所给出过的所有回答都相符。