P15851 [NOISG 2026 Finals] 柠檬 / Lemon【暂无数据】
题目描述
**这是一道交互题。请注意，本题仅允许使用 C++ 语言。**
Takina 和 Chisato 正在参加一个水果大会。在与他们最喜欢的水果角色扮演者合影一天后，他们发现了一个游戏摊位。
游戏规则如下：
- 共有 $n$ 个水果，每个水果都有一个从 $1$ 到 $n$ 的**互不相同的**标签。
- 其中恰好有一个水果是柠檬，但 Takina 和 Chisato 目前都不知道是哪一个。
- Takina 将**依次**获得所有 $n$ 个水果。她的目标是将柠檬的标签传达给 Chisato（在此过程中 Chisato 被蒙着眼睛）。
在收到任何水果之前，Takina 会获得一个数组 $p$，它表示水果标签出现的顺序。$p[1]$ 是第一个水果的标签，$p[2]$ 是第二个水果的标签，依此类推。然后，Takina 会写下一个仅包含 `0` 和 `1` 的二进制字符串 $b$。该字符串的长度不能超过 $5000$ 个字符，但可以是空的。令 $x$ 表示 $b$ 的长度。
之后，水果将按照上述顺序**依次**交给 Takina。每收到一个水果，Takina 都会被告知它是否是柠檬。
- 如果该水果**不是**柠檬，Takina 可以选择是否吃掉它。这个决定必须在收到下一个水果之前做出，并且不能更改。
- 如果该水果**是**柠檬，Takina **不得**吃掉它。
令 $y$ 表示 Takina 吃掉的水果总数。
最后，Chisato 会收到字符串 $b$ 以及**未被吃掉的水果标签的排序列表**。利用这些信息，Chisato 必须确定哪个水果是柠檬。
Takina 和 Chisato 决定玩这个游戏 $t$ 次。请为他们设计一个策略，以在正确识别柠檬的同时，最小化 $x$ 和 $y$。
### 实现细节
这是一道交互题。**不要**从标准输入读取或向标准输出写入。
你需要实现**三个**过程。
对于 Takina，你需要实现：
```cpp
std::string init(int subtask, int n, std::vector p)
```
- `subtask`：测试用例所属的子任务索引。
- `n`：水果的数量。
- `p`：一个长度为 $n + 1$ 的数组，其中：
- $p[0] = 0$，且
- 对于每个 $1 \le i \le n$，$p[i]$ 是第 $i$ 个交给 Takina 的水果的标签。
- 此过程在每个测试用例中会被调用 $t$ 次，每次游戏开始时调用一次。
此过程应返回字符串 $b$，其长度在 $0$ 到 $5000$（含）之间，且仅由 `0` 和 `1` 组成。如果返回的字符串长度或格式无效，你将收到 Wrong Answer 的判定。
```cpp
bool receive_fruit(int id, bool is_lemon)
```
- `id`：交给 Takina 的水果的标签。
- `is_lemon`：如果给出的水果是柠檬，则为 `true`；否则为 `false`。
- 此过程在 $t$ 次游戏的每一次中，都会被调用 $n$ 次，每次对应一个水果。
此过程应返回 `true` 表示应该吃掉该水果，返回 `false` 表示不应该吃掉。如果在 `is_lemon` 为 `true` 时返回 `true`，你将收到 Wrong Answer 的判定。
对于 Chisato，你需要实现：
```cpp
int answer(int subtask, int n, std::string b,
std::vector uneaten)
```
- `subtask`：测试用例所属的子任务索引。
- `n`：水果的数量。
- `b`：由 `init` 返回的字符串。
- `uneaten`：一个长度为 $n - y + 1$ 的已排序向量，包含未被 Takina 吃掉的水果标签，其中：
- `uneaten[0] = 0`，且
- `uneaten[i]` 是未被吃掉的水果中第 $i$ 小的标签。
- 此过程在每个测试用例中会被调用 $t$ 次，每次游戏结束时调用一次。
此过程应返回一个整数，即柠檬的标签。如果返回值与正确的标签不匹配，你将收到 Wrong Answer 的判定。
在实际评测中，一个调用上述过程的程序会被运行**两次**：
1. 在第一次运行中，以下步骤会执行 $t$ 次：
- `init` 被调用一次。
- `receive_fruit` 被调用 $n$ 次，遵循交给 Takina 的水果顺序。
- 你的程序可以在连续调用之间存储和保留信息。
2. 在第二次运行中，**游戏的顺序可能与第一次运行不同**。对于 $t$ 次游戏中的每一次：
- `answer` 被调用一次。除了传递给 `answer` 的参数外，你的程序**不得**访问第一次运行中的信息。
由于过程可能被多次调用，你应注意前一次调用留下的数据对当前调用的影响。
输入格式
输入的第一行包含一个整数 `subtask`。
输入的第二行包含一个整数 $t$。
接下来的 $t$ 行输入每行描述一次游戏。每次游戏由以下内容描述：
- 一行包含两个由空格分隔的整数 $n$ 和 $l$，分别表示水果的数量和柠檬的标签，以及
- 一行包含 $n$ 个由空格分隔的整数 $p[1], p[2], \dots, p[n]$。
```
subtask
t
n_1 l_1
p_1[1] p_1[2] ... p_1[n_1]
n_2 l_2
p_2[1] p_2[2] ... p_2[n_2]
...
n_t l_t
p_t[1] p_t[2] ... p_t[n_t]
```
输出格式
样例评测器输出一个实数，表示根据所有游戏中 $x$ 和 $y$ 的值计算出的得分比例。
说明/提示
### 样例交互
考虑一个单次游戏（$t = 1$），$n = 4$。请注意，这不满足输入约束，仅在此用于演示目的。
假设 Takina 获得的水果顺序为 $p = [0, 3, 1, 4, 2]$。
这意味着水果将按以下标签顺序呈现：$3, 1, 4, 2$。
假设标签为 $4$ 的水果是柠檬。
首先，调用 `init`。Takina 接收参数 `subtask`、`n` 和 `p`，并返回字符串 $b$。
然后，对于给定顺序中的每个水果，依次调用 `receive_fruit`。每次，Takina 被告知该水果是否是柠檬，并决定是否吃掉它。
最后，Chisato 收到字符串 $b$ 和未被吃掉的水果标签的排序集合，并调用过程 `answer`。
一种可能的调用和返回值序列如下所示。
| 步骤 | 过程调用 | 参数 | 返回值 |
|:----:|:----------------:|:-----------------------------------:|:--------:|
| 1 | `init` | `(subtask, 4, [0, 3, 1, 4, 2])` | `"101"` |
| 2 | `receive_fruit` | `(3, false)` | `true` |
| 3 | `receive_fruit` | `(1, false)` | `false` |
| 4 | `receive_fruit` | `(4, true)` | `false` |
| 5 | `receive_fruit` | `(2, false)` | `true` |
| 6 | `answer` | `(subtask, 4, "101", [0, 1, 4])` | `4` |
在此示例中，Takina 吃掉了标签为 $3$ 和 $2$ 的水果，因此未被吃掉的水果是 $\{1, 4\}$。传递给 `answer` 的向量 `uneaten` 因此是 `[0, 1, 4]`。
利用 $b$ 和 `uneaten`，过程 `answer` 返回 $4$，即柠檬的标签。此策略能够以 $x = 3$ 和 $y = 2$ 正确识别柠檬。
### 测试
你可以在附件中下载样例评测器（`grader.cpp`）、头文件（`lemon.h`）和一个解决方案模板（`lemon.cpp`）。提供了两个输入文件供你测试：`sample1.txt` 和 `sample2.txt`。你可以使用脚本 `compile.sh` 来编译，使用 `run.sh` 来运行你的解决方案进行测试。
**本题不支持 CMS 用户测试。**
提供了一个样例评测器来帮助你在本地测试你的实现。与官方评测器不同，样例评测器只运行你的程序**一次**，并且不会改变 Takina 和 Chisato 的测试顺序。
可能会向标准错误输出额外的诊断信息。样例评测器**不**模拟官方评测器的行为。
### 子任务
对于所有测试用例，输入数据满足以下限制：
- $1 \le t \le 10\,000$
- $n = 500$
- 对于所有 $1 \le i \le n$，有 $1 \le p[i] \le n$
- 恰好有一个柠檬。
对于每个子任务，你的程序将根据 Takina 写下的字符串长度 $x$ 和她吃掉的水果数量 $y$ 以不同方式计分。你在每个测试用例中的得分是根据所有 $t$ 次游戏中 $x$ 的最大值和所有 $t$ 次游戏中 $y$ 的最大值计算的。
| 子任务 | 得分公式 |
|:-------:|:-----:|
| 1 | 如果 $y > 2$，你的得分为 $0$。否则，你的得分为 $10 \times \min\left(\frac{288}{x}, 1\right)$。 |
| 2 | 如果 $y > 9$，你的得分为 $0$。否则，你的得分为 $30 \times \min\left(\frac{30}{x}, 1\right)$。 |
| 3 | 你的得分为 $60 \times \min\left(\frac{20}{x+y}, 1\right)$。 |
翻译由 DeepSeek V3.2 完成