题目描述

这是一道交互题。

有 $n$ 种细菌，编号从 $0$ 到 $n-1$。有一些种类的细菌是有毒的，另一些是正常的。保证至少有 $1$ 类细菌有毒，$1$ 类细菌正常。现在我们想通过设计实验确定哪些种类的细菌是有毒的。

实验流程是把若干（不超过 $1000$）个细菌放到一行培养皿上，然后观察每分钟存活细菌的数量。注意：你可以在培养皿上放置多个同类的细菌。每一轮中，如果某个细菌是正常的且它的左边或者右边紧挨着有毒的细菌，那么这个正常的细菌就死亡了。每一轮细菌死亡后，实验机器会自动地把所有当前还存活着的细菌按照之前的相对顺序紧挨着排列。直到存活细菌的数量不发生变化，这一次实验就结束了。

由于做实验需要时间和金钱，所以想用尽可能少的实验次数来确定每种细菌是否有毒。

交互格式

这是一道交互题。请不要尝试从文件输入输出中读写数据。 你需要实现下列函数：

void determine_type(int n)

这个函数在每次测试时只会被调用一次。$n$ 表示细菌种类数。 你可以使用交互库中的下列函数来完成任务：

std::vector<int> query_machine(std::vector<int> samples)

void answer_type(std::vector<char> v)

query_machine 的参数是一个向量，表示具体把哪些细菌放到一行培养皿上进行实验，samples[i] 表示培养皿的第 $i$ 个格子上是哪种细菌。samples 的长度不能超过 $1000$，且包含的数字应该在 $[0, n-1]$ 的范围内。并且，samples 在 query_machine 中是不会被修改的，你可以假定 samples 在调用 query_machine 前后不发生变化，这可能对你的代码实现有帮助。query_machine 将会返回一个向量，表示每轮存活的细菌数量。

answer_type 是在你确定下来所有细菌是否有毒后提交答案时调用的函数，参数必须是 $n$ 个字符构成的向量。第 $i$ 个字符表示第 $i$ 种细菌有毒（"T"）或者正常（"R"）。

下面的情况将会导致你收到 WA 的评测结果并且交互库的运行会马上终止：

• 调用 query_machine 超过 $1000$ 次或者某次调用时传递的向量长度超过 $1000$。
• 调用 answer_type 超过 $1$ 次。
• 传递给 answer_type 的向量长度不为 $n$ 或者某个字符既不是 "T"，又不是 "R"。
• 在调用 answer_type 后还在调用 query_machine。
• 在实现的 determine_type 函数结束时还没有调用 query_machine。

注意：交互库不是自适应的，这意味着每个测试点的结果（即每种细菌是否有毒）是一开始确定下来的，而不是根据你的询问动态调整的。

交互流程示例

只在此样例中，$n = 3$。在其他所有的测试样例中，$n = 1000$。如果你的程序不能解决 $n = 3$ 的情况，也是无所谓的。
假设第 $0$ 种细菌有毒，而第 $1 2$ 种细菌正常。
交互库将会用 $n = 3$ 去调用你实现的函数：

determine_type(3)

你可能设计的实验步骤如下：

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

由于第 $0$ 种细菌有毒，第 $12$ 种细菌正常，所以第一轮第 $0$ 种细菌左右的两个细菌就死亡了。列出现在还活着的细菌，就是 $[0, 1]$，还有 $2$ 个，因此返回的向量的第一个元素是 $2$。
现在活着的细菌就是 $[0]$，还有 $1$ 个，因此返回的向量的第二个元素是 $1$。
由于此后存活的细菌数量不变了，所以实验在两轮后就结束了，所以返回的向量长度为 $2$。
此时，你可能觉得已经拥有了足够的信息，确定第 $0$ 种细菌有毒，而第 $1\ 2$ 种细菌正常，所以你调用

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

提交答案。由于该程序已成功识别出所有细菌是否有毒，且查询次数不超过 $1000$ 次，未出现任何非法调用，因此该测试用例将被认为是正确的。

数据范围

对于所有测试点，$n = 1000$。保证至少有 $1$ 类细菌有毒，$1$ 类细菌正常。分两个子任务：
子任务 1 (10 分)：保证第 $0$ 种细菌是有毒的。在该子任务下，你只需要查询次数不超过 $1000$ 次就可以得到所有分数。
子任务 2 (90 分)：无特殊性质。在该子任务下，设你调用 query_machine 函数的次数为 $q$。若 $q > 1000$，则会被判定为 WA。若 $q\le 21$ 则 AC。若 $21< q <= 1000$，你得到的分数用下列公式计算：

$$81 \times\sqrt{\frac{21}{q}}$$

所以 $q=21$ 和 $q=22$ 得分差距会很大。

每个子任务的分数为该子任务下所有测试点得分的最小值。

如何测试你的程序（仅针对 C++ 语言）

下面给出在 Linux 环境下的测试，对于 windows 环境可以类似处理（基本只有可执行文件的命名方式变化）。

下发了两个交互库输入文件。其中 sample1.in sample2.in 是样例输入。
sample.cpp 是对 determine_type 函数的一个样例实现。你需要在此基础上进行修改，在 NOI 赛制中你需要提交的程序文件名仍然应为 toxic.cpp，但在此 OJ 上提交对文件名不作要求。
toxic.h 是函数声明的头文件，你提交的 toxic.cpp 必须包含此头文件，否则可能会出现编译错误。
在你实现好 toxic.cpp 以后，使用下面命令可以编译得到可执行文件 toxic：

g++ --std=c++14 -O2 -o toxic toxic.cpp stub.cpp

stub.cpp 是下发的交互库文件，交互库（或者说是你编译好的可执行文件 toxic）将会从标准输入中读取一个整数 n，再读取 n 个字符，表示每种细菌是否有毒。然后交互库会调用你在 toxic.cpp 中实现的 determine_type(n) 函数，并且检查正确性。在你实现的函数给出正确判断之后，交互库会在标准输出中输出正确信息和你调用 query_machine 函数的次数。如果出现任何非法调用，交互库也会给出错误信息。 注意：下发的交互库和测试时使用的交互库不完全相同，不要试图修改交互库的输入和输出，以免出现未知错误。

提示

题目顺序是瞎排的。