P10802 [CEOI 2024] 核酸检测
题目描述
**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day1 T2「[COVID tests](https://ceoi2024.fi.muni.cz/page/tasks/statements/covid.pdf)」**
亚当的学校最近爆发了新一波 COVID 疫情。为了防止疫情进一步蔓延，学校决定用唾液抗原检测试剂对所有学生进行检测。
由于老师们很久没用过这些试剂了，亚当自告奋勇地成为了检测志愿者。他拿到了来自 $N$ 个学生的唾液样本（出于隐私保护，他只能看到编号从 $0$ 到 $N-1$ 的标识符），他的任务是确定哪些样本呈阳性。
然而，亚当很快意识到，挨个检测所有学生的样本实在太耗时费力了。他灵机一动，想到了一种比逐个检测更巧妙的方法。如果他将部分样本混合在一起进行检测，他就能知道整个混合物是全部阴性，还是至少有一个阳性。这样一来，他就可以通过这种方式减少所需的检测次数！
每个样本的唾液量都足够进行多次检测。而且，这些检测试剂非常精准，同一个样本绝不会出现不同的检测结果。
在这样的条件下，亚当希望优化检测流程，尽量减少使用的检测次数。但是他目前正在进行检测，所以优化过程就交给你啦！
通过当地的统计数据，亚当了解到任何一个样本呈阳性的概率都等于 $P$，并且一个样本是阳性还是阴性不会影响其他样本的检测结果。也许你可以利用这些信息来帮助亚当优化检测方案？
输入格式
这是一道交互题。
你的程序将会处理若干个测试数据。每个测试数据（即程序的一次运行）中，你需要解决 $T$ 个不同的场景。所有场景中，学生数量 $N$ 和阳性样本概率 $P$ 都保持不变，但是哪些学生的样本呈阳性（很可能）在每个场景中都会不同。
你可以自己实现交互协议，也可以使用提供的模板。你可以在「文件」中找到名为 `template.cpp` 的附件，它就是提供的模板。
首先，你的程序应该从标准输入读取一行，包含空格隔开的三个整数 $N, P, T$，分别表示学生数量、阳性样本概率和场景数量。
然后，程序可以向标准输出输出询问信息。每个询问信息应该单独占一行，格式为 `Q`、空格和一个长度为 $N$ 的字符串 $s$。字符串 $s$ 中的每个字符 $s_i$ 都为 `1` 或 `0`，`1` 表示应该将第 $i$ 个学生的样本加入混合物进行检测，`0` 表示不加入。输出完询问信息后，程序需要刷新标准输出缓冲区，然后从标准输入读取一个字符。这个字符会是 `P`（表示混合物中至少有一个样本呈阳性）或 `N`（表示混合物中所有样本均为阴性）。
程序也可以输出最终答案。答案信息应该单独占一行，格式为 `A`、空格和一个长度为 $N$ 的字符串 $s$。字符串 $s$ 中的每个字符 $s_i$ 都为 `1` 或 `0`，`1` 表示第 $i$ 个学生的样本呈阳性，`0` 表示呈阴性。输出完答案信息后，程序同样需要刷新标准输出缓冲区，然后从标准输入读取一个字符。
如果读取到的字符为 `C`，则表示你的答案正确。在这种情况下，程序可以开始处理下一个场景的询问，或者如果是第 $T$ 个场景的答案，则程序可以退出。
如果读取到的字符为 `W`，则表示你的答案错误。程序应该立即退出。
请注意，在收到 `W` 后退出对于交互器给出正确的反馈非常重要。如果你的程序继续运行，它可能会崩溃或收到其他错误的判定。
交互器不会根据你的程序运行结果来动态调整测试数据。这意味着每个样本的阳性与否会在程序运行之前就确定好。并且，每个样本的阳性与否都是通过公平的随机数生成器，以概率 $P$ 独立决定的。
如果你使用 `template.cpp` 中的交互协议实现，你需要实现函数 `std::vector find_positive()`。这个函数会在每个场景中被调用一次。它需要返回一个长度为 $N$ 的布尔型向量，其中第 $i$ 个元素为 `true` 当且仅当第 $i$ 个学生的样本呈阳性。
实现过程中，你可以使用函数 `bool test_students(std::vector mask)`。这个函数可以对部分样本进行混合检测。它唯一的参数是一个长度为 $N$ 的布尔型数组，其中第 $i$ 个元素为 `true` 表示应该将第 $i$ 个样本加入混合物进行检测。该函数返回 `true` 当且仅当混合物中至少有一个样本呈阳性。
你也可以使用全局变量 `N` 和 `P`，它们分别代表着总学生人数和阳性样本概率。你可以在 `main` 函数中，首次调用 `scanf` 之后进行初始化操作。
| 示例输入 | 示例输出 |
|------------|----------------|
| `10 0.4 2` | |
| | `Q 1000000000` |
| `P` | |
| | `Q 0000001000` |
| `P` | |
| | `Q 0000000001` |
| `P` | |
| | `Q 0111110110` |
| `N` | |
| | `A 1000001001` |
| `C` | |
| | `A 0000000000` |
| `W` | |
输出格式
无
说明/提示
本题分为两个子任务。
#### Subtask 1 (10 分)
- 学生总数 $N = 1000$
- 场景数 $T = 1$
- 阳性样本概率 $P$ 在 $0$ 到 $1$ 之间
如果程序能正确回答并且每个测试数据的询问次数不超过 $2$ 倍的总学生人数 $2N$，则认为该程序通过测试。
#### Subtask2 (90 分)
- 学生总数 $N = 1000$
- 场景数 $T = 300$
- 阳性样本概率 $P$ 在 $0.001$ 到 $0.2$ 之间
该子任务具有部分分。
如果你的程序在任何场景的回答错误，你将得 $0$ 分。否则，每个测试数据的得分将基于平均询问次数计算。一般来说，询问次数越少，得分越高。记作程序在所有场景的平均询问次数为 $Q$，四舍五入到小数点后一位。对于每个测试数据，我们计算了一个值 $F$（见下文）。给定测试数据的得分将根据以下规则计算：
- 如果 $Q > 10$ 倍的 $F$，你将得 $0$ 分 (错误答案)。
- 如果 $F < Q \leq 10$ 倍的 $F$，得分由以下公式计算：
$$ 90 \cdot \frac{F}{F + 4 \cdot (Q-F)} $$
- 如果 $Q \leq F$，你将获得满分 $90$ 分。
你的程序将会在不同 $P$ 值的测试数据上进行评分。你将获得的总分是所有测试数据（所有概率 $P$）中的最低分。
测试数据如下：
| $P$ | $F$ |
|-------|-------|
| $0.001$ | $15.1$ |
| $0.005256$ | $51.1$ |
| $0.011546$ | $94.9$ |
| $0.028545$ | $191.5$ |
| $0.039856$ | $246.3$ |
| $0.068648$ | $366.2$ |
| $0.104571$ | $490.3$ |
| $0.158765$ | $639.1$ |
| $0.2$ | $731.4$ |
交互器会为每个测试数据提供反馈。这些反馈将包括你在得分非零的测试数据上的平均询问次数 $Q$。