Toxic Gene

题目描述

本题为函数式交互 / Grader 题，仅支持 C++。

Benson 的飞机被有毒细菌污染了。现在有 $n$ 种细菌，编号为 $1,2,\ldots,n$。每种细菌恰好属于以下三类之一：

• R：普通细菌（Regular）；
• S：强壮细菌（Strong）；
• T：有毒细菌（Toxic）。

其中有 $t$ 种有毒细菌，保证：

$$1\le t\le 30.$$

你不知道 $t$ 的值，也不知道每种细菌的类别。你的任务是确定所有细菌的类别。

你可以把若干细菌样本放入检测机器中。一次检测中，你可以指定一个细菌种类序列，同一种细菌可以出现多次，也可以完全不出现。一次检测中放入机器的细菌总数不能超过 $300$。

不同类别细菌的存活规则如下：

• 普通细菌：如果样本中没有有毒细菌，则存活；如果样本中至少有一个有毒细菌，则死亡；
• 强壮细菌：无论样本中是否存在有毒细菌，都会存活；
• 有毒细菌：会释放毒素，使样本中所有非强壮细菌死亡；有毒细菌自身也会死亡。

机器会返回本次样本中最终存活的细菌数量。

每次调用机器都需要花费时间。对于每次 determine_type 调用，你最多只能调用检测函数 $600$ 次。你需要在限制内确定所有细菌的类别，并尽量减少检测次数。

需要实现的函数

选手需要提交一个 C++ 源文件，包含头文件：

#include "toxic.h"

并实现函数：

void determine_type(int n);

该函数会被评测程序调用。每次调用中，细菌种数为 n，你需要通过下方 grader 函数判断所有细菌的类别。

你的程序不要读入标准输入，也不要输出到标准输出，并且不要实现 main 函数。

可调用函数

你可以调用以下两个函数。

query_sample

int query_sample(std::vector<int> species);

参数 species 表示本次放入机器的细菌种类序列。species 的长度不能超过 $300$。其中每个元素必须是 $1$ 到 $n$ 之间的整数。

该函数返回本次样本中最终存活的细菌数量。

answer_type

void answer_type(int x, char c);

当你确定第 $x$ 种细菌的类别时，调用该函数提交答案。

其中 c 必须是以下字符之一：

• 'R'：普通细菌；
• 'S'：强壮细菌；
• 'T'：有毒细菌。

你必须对所有 $1\le x\le n$ 调用一次 answer_type，并且答案必须正确。

判错条件

出现以下任意情况，评测程序会立即输出 -1 并结束：

• query_sample 或 answer_type 的参数非法；
• 某次 answer_type 给出的类别错误；
• determine_type 结束时仍有细菌没有被回答；
• 某次 determine_type 中调用 query_sample 超过 $600$ 次。

评测程序不是自适应的，即每个测试点中的真实答案在程序运行前已经固定，不会根据你的询问改变。

数据范围

对于所有正式测试数据：

$$n=300,$$ $$1\le t\le 30.$$

每个测试点中，determine_type 最多会被调用 $100$ 次。不同调用中的细菌类别分布可能不同。

计分方式

设你的程序在所有测试点、所有 determine_type 调用中的最大询问次数为 $m$。

• 若 $m>600$，得分为 $0$；
• 若 $340<m\le 600$，得分为

$$2+7\times\frac{600-m}{260};$$

• 若 $275<m\le 340$，得分为

$$9+15\times\frac{340-m}{65};$$

• 若 $190<m\le 275$，得分为

$$24+22\times\frac{275-m}{85};$$

• 若 $150<m\le 190$，得分为

$$46+54\times\frac{190-m}{40};$$

• 若 $m\le 150$，得分为 $100$。

样例交互说明

假设 $n=5$，第 $1,2$ 种细菌是有毒细菌，第 $3,4$ 种细菌是普通细菌，第 $5$ 种细菌是强壮细菌，对应字符串为：

TTRRS

一次可能的交互如下：

query_sample({1, 2, 3, 4, 5})

样本中存在有毒细菌，因此普通细菌和有毒细菌都会死亡，只有第 $5$ 种强壮细菌存活，返回值为 $1$。

query_sample({3, 3, 4, 5})

样本中没有有毒细菌，因此所有样本都存活，返回值为 $4$。

之后可以提交：

answer_type(1, 'T');
answer_type(2, 'T');
answer_type(3, 'R');
answer_type(4, 'R');
answer_type(5, 'S');

如果全部正确且询问次数不超过限制，则该次调用通过。

注意：该样例只用于解释交互方式，不满足正式数据范围。

提交模板

#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;

void determine_type(int n) {
    // 在这里实现你的算法。
}

本地测试说明

下发文件中提供了官方本地测试文件：

• toxic.h：接口头文件；
• toxic.cpp 或 template.cpp：提交模板；
• stub.cpp：本地测试用 grader；
• sample1.txt、sample2.txt：本地测试输入；
• compile.sh：本地编译脚本。

在 Linux/macOS 环境下，可以运行：

chmod +x compile.sh
./compile.sh
./toxic < sample1.txt
./toxic < sample2.txt

如果程序错误，grader 会输出 -1；否则会对每次 determine_type 调用输出一行整数，表示该次调用使用了多少次 query_sample。

正式提交时只需要提交实现了 determine_type 的源代码，评测系统会自动提供正式 grader 和 toxic.h。

@下发文件