这是一个交互式任务。注意，此任务仅支持 C++。

在成功研究了有毒细菌后，Benson the Rabbit 退休了！外星人 James 接管了他的实验室，并最近发现了一种他想要研究的新型细菌！

James 有 $n$ 种细菌，编号为 $0$ 到 $n-1$。每种细菌恰好属于以下两种类型之一：普通（Regular）或有毒（Toxic）。其中有 $t$ 种是有毒的。保证至少有 $1$ 种有毒细菌和 $1$ 种普通细菌，即 $1 \le t < n$。注意，James 不知道 $t$ 的值。

James 想要识别每种细菌的类型。为了分析这些细菌，他买了一台新机器来代替 Benson 的旧机器！这台新机器允许 James 在一行中放置最多 $1000$ 个细菌样本。每个样本由单一物种组成，且允许多个样本属于同一物种。

在 James 选择好样本后，机器将运行若干轮迭代。在每一轮迭代中，任何与有毒细菌样本相邻的普通细菌样本都会死亡。随后，机器会将所有存活的细菌样本移动以填补空隙，使得剩余的细菌形成一行。

机器将持续运行，直到下一轮迭代中存活的细菌数量与当前迭代相同。这意味着机器至少会运行 $1$ 轮，即使在第一轮中没有细菌死亡。

机器随后会向 James 报告每一轮迭代后存活的细菌样本数量。这构成一次查询。每次使用机器都需要时间，而 James 的时间有限。他最多只能使用机器 $1000$ 次。请帮助 James 以尽可能少的查询次数确定每种细菌是普通还是有毒。

实现细节

这是一个交互式任务。请勿从标准输入读取或向标准输出写入。

你需要实现以下函数：

• void determine_type(int n)

该函数在每个测试用例中会被调用恰好一次。函数将传入 $n$，代表 James 拥有的细菌种类数量。

你可以调用以下评测库函数来完成任务：

• std::vector<int> query_machine(std::vector<int> samples)
• void answer_type(std::vector<char> v)

函数 query_machine 被调用时传入一个一维数组 samples，描述你放入机器中的细菌种类，顺序为你放置的顺序。samples 的大小不能超过 $1000$，且必须包含 $0$ 到 $n-1$ 之间的整数。此外，传入 query_machine 的向量不会被修改。换句话说，你可以预期在调用 query_machine 后 samples 向量保持不变。

该函数将返回一个向量，表示直到机器停止运行前，每一轮迭代后存活的细菌样本数量。

函数 answer_type 必须传入一个恰好包含 $n$ 个字符的向量，其中第 $i$ 个字符代表第 $i$ 种细菌的类型。向量中的每个字符可以是 ‘R’ 或 ‘T’，分别代表普通细菌和有毒细菌。

以下情况将导致你收到 Wrong Answer 判决并使程序立即终止：

• 如果 query_machine 被调用超过 $1000$ 次，或单次调用中包含超过 $1000$ 个样本
• 如果 answer_type 被调用超过一次
• 如果传入 answer_type 的向量没有恰好 $n$ 个元素，或者包含错误的细菌类型
• 如果在调用 answer_type 后调用了 query_machine
• 如果在 determine_type 终止时尚未调用 answer_type

请注意，此任务的评测库不是自适应的。这意味着每个测试用例的答案是固定的，在程序执行期间不会改变。

样例

在本示例中，$n = 3$。在所有其他测试用例中 $n = 1000$。你的程序不需要解决此样例即可被视为正确。

假设细菌种类 $0$ 是有毒的，而细菌种类 $1$ 和 $2$ 是普通的。你的函数将被调用，参数如下：

determine_type(3)

可能的交互过程如下：

• query_machine([1, 0, 2, 1]) = [2, 1]

此调用表示放入 $1$ 个种类 $0$ 的样本， $1$ 个种类 $2$ 的样本，以及 $2$ 个种类 $1$ 的样本，顺序为 [1, 0, 2, 1]。

在第一轮迭代中，第一个样本（种类 $1$）和第三个样本（种类 $2$）因为与有毒种类 $0$ 相邻而被杀死。此后，剩余 $2$ 个存活的细菌样本，[0, 1]。

在第二轮迭代中，第二个样本（种类 $1$）被杀死。此后，剩余 $1$ 个存活的细菌样本，[0]。此时，任何后续迭代也将剩余 $1$ 个存活的细菌样本，因此机器终止并返回每一轮迭代后存活的样本数量：[2, 1]。

• query_machine([1, 0, 1, 0, 0]) = [3]

在第一轮迭代中，第一个和第三个样本（种类 $1$）都会死亡。此后，剩余 $3$ 个存活的细菌样本，[0, 0, 0]。此时，任何后续迭代也将剩余 $3$ 个存活的细菌样本，因此机器终止并返回：[3]。

• query_machine([2, 1]) = [2]

在第一轮迭代中，没有细菌死亡。此时，任何后续迭代也将剩余 $2$ 个存活的细菌样本，因此机器终止并返回：[2]。

此时，程序决定它已有足够的信息来确定细菌类型，并进行以下调用：

• answer_type(['T', 'R', 'R'])

此调用不返回任何值。由于程序已正确识别所有 $n = 3$ 种细菌的类型，使用的查询次数不超过 $1000$ 次，且未进行任何无效调用，因此该测试用例将被视为正确。

数据范围

你的程序将在满足以下限制的输入实例上进行测试：

• $n = 1000$
• $1 \le t < 1000$

子任务

子任务 2 是一个部分分任务。你的得分取决于你在该子任务中所有测试用例上进行的查询总数，记为 $q$。

• 如果 $q > 1000$，得分为 $0$。
• 如果 $21 < q \le 1000$，得分为 $90 \times \sqrt{\frac{21}{q}}$。
• 如果 $q \le 21$，得分为 $90$。

测试

你可以从附件中下载评测库文件、头文件和解决方案模板。提供了两个输入文件供你测试，sample1.txt 对应样例交互中的测试用例，sample2.txt 包含一个 $n = 1000$ 的测试用例。请使用脚本 compile.sh 编译并运行你的解决方案进行测试。

测试用的评测库输入格式

第一行包含一个整数 $n$，即细菌种类的数量。

下一行包含一个长度为 $n$ 的字符串（由 ‘R’ 或 ‘T’ 组成），按顺序描述所有细菌的类型。

测试用的评测库输出格式

对 determine_type 的调用结果打印在单行上。

如果你的程序进入了触发 Wrong Answer 判决的任何情况，评测库会打印相应的 Wrong Answer 信息并立即终止。

否则，评测库会输出对 query_machine 的调用次数。注意，与实际评测库不同，样例评测库在调用 query_machine 超过 $1000$ 次时不会立即终止。