P8494 [IOI 2022] 最罕见的昆虫
题目背景
# 滥用评测资源者封号
**本题为交互题。**
您**不需要也不应该**在提交的程序中包含 `insects.h` 头文件和主函数。
但是在您的程序中，需要声明以下三个函数：
```cpp
void move_inside(int i);
void move_outside(int i);
int press_button();
```
例如，您的程序可以是这样：
```cpp
#include
using namespace std;
void move_inside(int i);
void move_outside(int i);
int press_button();
int min_cardinality(int N) {
// Code Here
}
```
题目描述
Pak Blangkon 的房子四周有 $N$ 只昆虫，编号为 $0$ 至 $N-1$。每只昆虫有一个**类型**，以从 $0$ 至 $10^9$（包含 $0$ 和 $10^9$）的整数编号。可能有多只昆虫类型相同。
假设将昆虫按照类型分组。我们定义**最常见**昆虫类型的基数是昆虫最多的分组中的昆虫数。类似地，**最罕见**昆虫类型的基数是昆虫最少的分组中的昆虫数。
例如，假设有 $11$ 只昆虫，类型分别为 $[5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]$。在此情形中，**最常见**昆虫类型的基数是 $3$，是因为类型 $9$ 和类型 $11$ 的分组均有最多数目的昆虫，每个分组都有 $3$ 只。**最罕见**昆虫类型的基数是 $1$，是因为类型 $7$、类型 $0$ 和类型 $100$ 的分组均有最少数目的昆虫，每个分组都有 $1$ 只。
Pak Blangkon 不知道这些昆虫的类型。他有一台单按钮的机器，可以提供昆虫类型相关的信息。刚开始时，机器是空的。在使用机器时，可以做如下三种操作：
1. 将一只昆虫放进机器。
2. 将一只昆虫取出机器。
3. 按下机器的按钮。
每种操作最多可以做 $40\;000$ 次。
每当按下按钮时，机器会报告在机器内的**最常见**昆虫类型的基数。
你的任务是使用上述机器，确定 Pak Blangkon 的房子四周所有 $N$ 只昆虫中**最罕见**昆虫类型的基数。此外，在某些子任务里，你的得分取决于机器执行某种操作的最大次数（详见子任务一节）。
输入格式
无
输出格式
无
说明/提示
### 约束条件
- $2 \le N \le 2000$。
### 子任务
1. （10 分） $N \le 200$；
2. （15 分） $N \le 1000$；
3. （75 分） 没有额外的约束条件。
如果在某个测试用例上，函数 `move_inside`、`move_outside` 或 `press_button` 的调用次数不符合“实现细节”中给出的约束条件，或者 `min_cardinality` 的返回值不正确，你的解答在此子任务上得分为 $0$。
令 $q$ 为以下三个值的 **最大值**：`move_inside` 的调用次数、`move_outside` 的调用次数、`press_button` 的调用次数。
在子任务 3 中，你可能会得部分分。令 $m$ 为此子任务所有测试用例的 $\frac{q}{N}$ 的最大值。你在此子任务的得分将根据以下表格计算：
| 条件 | 得分 |
| :--------------: | :--------------------------------------: |
| $20 \lt m$ | $0$ （CMS 报告“`Output isn’t correct`”） |
| $6 \lt m \le 20$ | $\frac{225}{m - 2}$ |
| $3 \lt m \le 6$ | $81 - \frac{2}{3} m^2$ |
| $m \le 3$ | $75$ |
### 评测程序示例
令 $T$ 是长度为 $N$ 的整数数组，其中 $T[i]$ 是编号为 $i$ 的昆虫的类型。
评测程序示例按以下格式读取输入：
- 第 $1$ 行：$N$；
- 第 $2$ 行：$T[0] \; T[1] \; \ldots \; T[N - 1]$。
如果评测程序示例检测到非法行为，评测程序示例将输出 `Protocol Violation: `，其中 `` 为如下某种类型：
- `invalid parameter`：在函数调用 `move_inside` 或 `move_outside` 时，参数 $i$ 的值不在 $0$ 至 $N-1$ 的范围内（包括 $0$ 和 $N-1$）。
- `too many calls`：函数 `move_inside`、`move_outside` 或 `press_button` 中**某个**的调用次数超过 $40\;000$ 次。
否则，评测程序示例按以下格式输出：
- 第 $1$ 行：`min_cardinality` 的返回值；
- 第 $2$ 行：$q$。
### 约定
题面在给出函数接口时，会使用一般性的类型名称 `void`、`bool`、`int`、`int[]`（数组）和 `union(bool, int[])`。
在 C++ 中，评测程序会采用适当的数据类型或实现，如下表所示：
| `void ` | `bool` | `int` | `int[]` |
| ------- | ------ | ------| ------------------ |
| `void ` | `bool` | `int` | `std::vector` |
| `union(bool, int[])` | 数组 `a` 的长度 |
| -------------------------------------- | ------------------- |
| `std::variant` | `a.size()` |
C++ 语言里，`std::variant` 定义在 `` 头文件中。
一个返回类型为 `std::variant` 的函数可以返回一个 `bool` 或一个 `std::vector`。
以下示例代码给出了三个返回 `std::variant` 的函数，它们都能正常工作：
```cpp
std::variant foo(int N) {
return N % 2 == 0;
}
std::variant goo(int N) {
return std::vector(N, 0);
}
std::variant hoo(int N) {
if (N % 2 == 0) {
return false;
}
return std::vector(N, 0);
}
```