注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "toxic.h"。

题目描述

译自 NOISG 2024 Final T3. Toxic Gene 2

在成功研究有毒细菌的职业生涯后，兔子本森退休了！外星人詹姆斯接管了他的实验室，最近发现了一种新型细菌，他希望对此进行研究！

詹姆斯有 $n$ 种细菌，编号从 $0$ 到 $n-1$。每种细菌恰好属于两种类型之一：常规（Regular）或有毒（Toxic）。其中 $t$ 种是有毒的。保证至少有 $1$ 种有毒细菌和 $1$ 种常规细菌，即 $1 \leq t < n$。注意，詹姆斯不知道 $t$ 的值。

詹姆斯希望确定每种细菌的类型。为了分析细菌，他购买了一台新机器替换本森的旧机器！这台新机器允许詹姆斯将最多 $1000$ 个细菌样本按顺序放置在一条直线上。每个样本属于单一物种，且允许多个样本属于同一物种。

詹姆斯选择好样本后，机器将运行若干次迭代。在每次迭代中，任何与有毒细菌样本相邻的常规细菌样本将死亡。机器随后将所有存活的细菌样本移位以填补空隙，使剩余细菌形成连续的一行。

机器将运行直到下一次迭代的存活细菌样本数量与当前迭代相同。这意味着机器至少运行 $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 调用，描述你放置在机器中的细菌物种，按放置顺序排列。samples 的大小不得超过 $1000$，且必须包含 $0$ 到 $n-1$ 的整数。此外，传递给 query_machine 的向量不会被修改。换句话说，调用 query_machine 后，samples 向量保持不变。

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

函数 answer_type 必须使用一个恰好包含 $n$ 个字符的向量调用，其中第 $i$ 个字符表示第 $i$ 种细菌的类型。向量中的每个字符可以是 R 或 T，分别表示常规细菌和有毒细菌。

以下情况将导致答案错误判定并立即终止程序：

• 如果 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,2,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 \leq t < 1000$

详细子任务附加限制及分值如下表所示：

子任务	分值	附加限制
$1$	$10$	细菌 $0$ 是有毒的
$2$	$90$	无附加限制

评分

子任务 2 存在部分分。你的得分取决于在该子任务所有测试用例中使用的查询次数总和，记为 $q$。

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

示例评测程序

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

输入格式

第一行包含一个整数 $n$，表示细菌物种数量。

第二行包含一个长度为 $n$ 的字符串（包含 R 或 T），按顺序描述所有细菌物种的类型。

输出格式

determine_type 的调用结果输出在一行。

如果你的程序进入任何答案错误的情况，交互器将输出相应的错误消息并立即终止。

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