P11537 [NOISG 2023 Finals] Toxic Gene

**这是一道交互题。** 本题只支持 C++ 提交，建议使用 C++17。 提交时不需要包含 toxic.h 头文件。 为了确保程序正常编译，你需要在你提交的程序开头加上如下函数声明语句： ```cpp int query_sample(std::vector species); void answer_type(int x, char c); ``` 如遇评测问题，请联系搬题人。

**建议仔细区分题面中的“种类”和“个体”。** 兔子 Benson 的飞机被有害病毒侵袭了，他必须对此展开调查！ Benson 发现了 $n$ 种病毒，每种病毒恰好属于三个类型之一：普通、强悍和毒害。保证至少有一种毒害病毒。 Benson 必须识别每种病毒的类型。为了分析之，他将使用一个特殊的机器。每一次，他可以选择任意数量的病毒（包括 $0$）制成标本，并将其放入机器中。受机器大小的影响，每个标本里不能有超过 $300$ 个病毒。每个病毒的种类由 Benson 任意指定。 标本放入机器后，其中三个类型的病毒会发生如下反应： - 当且仅当不存在毒害病毒，普通病毒可以存活。 - 强悍病毒总是存活。 - 毒害病毒产生有害物质并杀死强悍病毒外的所有病毒。因此，毒害病毒总是死亡。 对于每个样本，机器会告诉 Benson 有多少病毒存活。由于机器分析消耗太多时间，Benson 最多只能使用 $600$ 次机器。请帮助 Benson 确定每种病毒的类型：普通、强悍或毒害。 ### 实现细节 这是一道交互题。你需要实现如下函数： - `void determine_type(int n)` 每个测试数据中，该函数最多被调用 $100$ 次，每次调用将对应不同的病毒组合。对于每个测试数据，你必须保证所有调用不超过时间限制和空间限制。 你可以通过调用如下函数完成题目： - `int query_sample(std::vector species)` - `void answer_type(int x, char c)` 调用 `query_sample` 函数时，需传入一维数组 `species`，表示标本中你所选择的病毒种类。该数组的大小不能超过 $300$。此外，你可以假定该函数调用结束后，`species` 数组不会改变。 调用 `answer_type` 函数时，需传入一个整数 $x$ 和一个字符 $c$。当你确定第 $x$ 种病毒的类型时，调用该函数，其中 $c$ 是 `R`、`S` 或 `T` 之一，分别表示普通病毒、强悍病毒和毒害病毒。你必须对每种病毒都调用该函数。 下列情况可能导致你收到 Wrong Answer 反馈并立即结束评测： - `query_sample` 函数或 `answer_type` 函数的调用非法 - `answer_type` 函数给出的病毒种类有误 - `determine_type` 函数结束时，存在某种病毒未被 `answer_type` 确认 - 某次 `determine_type` 函数调用过程中，`query_sample` 被调用了超过 $600$ 次 请注意，题目中的交互库是**非自适应的**，即每个测试数据的答案被提前确定，且不会在交互过程中改变。

示例测试程序按如下格式读取输入数据： 第一行两个整数 $tc, n$。$tc$ 表示 `determine_type` 的调用次数。 接下来 $tc$ 行，每行一个字符串，由 `R`、`S` 和 `T` 组成，依次描述每种病毒的类型。

示例测试程序按如下格式输出信息： 对于每次 `determine_type` 的调用，输出一行一个整数：若反馈为 Wrong Answer，输出 $-1$；否则输出 `query_sample` 的调用次数。

### 调用示例 假定 $n=5$，第一种病毒和第二种病毒是毒害病毒，第三种病毒和第四种病毒是普通病毒，第五种病毒是强悍病毒。该情况可用字符串 `TTRRS` 表达。 你的函数会被这样调用： - `determine_type(5)` 一个可能的交互过程如下： - `query_sample([1,2,3,4,5]) = 1` 所有种类的病毒都被放置在标本中，只有种类 $5$ 的病毒存活，故返回 $1$。 - `query_sample([3,3,4,5]) = 4` 两个“第三种病毒”、一个“第四种病毒”和一个“第五种病毒”被放置在标本中。由于不存在毒害病毒，所有病毒均存活，故返回 $4$。 此时，程序认为其已经确认所有病毒的类型，故进行了如下 $5$ 次调用： - `answer_type(1,'T')` - `answer_type(2,'T')` - `answer_type(3,'R')` - `answer_type(4,'R')` - `answer_type(5,'S')` 这些函数都没有返回值。当程序正确地确认了 $n=5$ 种病毒的种类，且未使用超过 $600$ 次询问时，会在该测试点中被认为是正确的。 请注意，该示例仅供展示交互过程，不一定存在合理逻辑。 ### 得分细则 设 $t$ 表示毒害病毒的数量。保证测试数据中 $n=300$，$1\leq t\leq 30$。 某测试点中，你的得分与所有 `determine_type` 调用中，询问次数的最大值有关，设为 $m$。 - 当 $m>600$ 时，得分为 $0$。 - 当 $340