注意事项

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

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

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

题目描述

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$ 只昆虫中最罕见昆虫类型的基数。此外，在某些子任务里，你的得分取决于机器执行某种操作的最大次数（详见子任务一节）。

实现细节

你要实现以下函数：

int min_cardinality(int N)

• $N$：昆虫数量。
• 此函数应返回 Pak Blangkon 的房子四周所有 $N$ 只昆虫中最罕见昆虫类型的基数。
• 此函数恰好被调用一次。

该函数可调用以下几个函数：

void move_inside(int i)

• $i$：将被放进机器的昆虫编号。编号 $i$ 的取值范围是 $0$ 至 $N-1$（包含 $0$ 和 $N-1$）。
• 如果昆虫已在机器内，函数调用不会影响机器内昆虫的集合。但是，调用仍会被计入此类操作的次数。
• 此函数最多可以被调用 $40\;000$ 次。

void move_outside(int i)

• $i$：将被从机器中取出的昆虫编号。编号 $i$ 的取值范围是 $0$ 至 $N-1$（包含 $0$ 和 $N-1$）。
• 如果昆虫已在机器外，函数调用不会影响机器内昆虫的集合。但是，调用仍会被计入此类操作的次数。
• 此函数最多可以被调用 $40\;000$ 次。

int press_button()

• 此函数返回机器内最常见昆虫类型的基数。
• 此函数最多可以被调用 $40\;000$ 次。
• 评测程序不是适应性的。也就是说，所有 $N$ 只昆虫的类型在 min_cardinality 调用前已经确定。

例子

考虑在某个场景下，有 $6$ 只类型分别为 $[5, 8, 9, 5, 9, 9]$ 的昆虫。 函数 min_cardinality 的调用方式如下：

min_cardinality(6)

此函数按以下次序调用了 move_inside、move_outside 和 press_button。

函数调用	返回值	机器内的昆虫	机器内的昆虫类型
	$\\{\\}$	$[\ ]$
move_inside(0)		$\\{0\\}$	$[5]$
press_button()	$1$
move_inside(1)		$\\{0, 1\\}$	$[5, 8]$
press_button()	$1$
move_inside(3)		$\\{0, 1, 3\\}$	$[5, 8, 5]$
press_button()	$2$
move_inside(2)		$\\{0, 1, 2, 3\\}$	$[5, 8, 9, 5]$
move_inside(4)		$\\{0, 1, 2, 3, 4\\}$	$[5, 8, 9, 5, 9]$
move_inside(5)		$\\{0, 1, 2, 3, 4, 5\\}$	$[5, 8, 9, 5, 9, 9]$
press_button()	$3$
move_inside(5)
press_button()	$3$
move_outside(5)		$\\{0, 1, 2, 3, 4\\}$	$[5, 8, 9, 5, 9]$
press_button()	$2$

至此，已有充分信息表明，最罕见昆虫类型的基数是 $1$。 因此，函数 min_cardinality 应返回 $1$。

在这个例子里，move_inside 被调用 $7$ 次，move_outside 被调用 $1$ 次，press_button 被调用 $6$ 次。

约束条件

• $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: <MSG>，其中 <MSG> 为如下某种类型：

• 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<int>

union(bool, int[])	数组 a 的长度
std::variant<bool, std::vector<int>>	a.size()

C++ 语言里，std::variant 定义在 <variant> 头文件中。 一个返回类型为 std::variant<bool, std::vector<int>> 的函数可以返回一个 bool 或一个 std::vector<int>。 以下示例代码给出了三个返回 std::variant 的函数，它们都能正常工作：

std::variant<bool, std::vector<int>> foo(int N) {
    return N % 2 == 0;
}

std::variant<bool, std::vector<int>> goo(int N) {
    return std::vector<int>(N, 0);
}

std::variant<bool, std::vector<int>> hoo(int N) {
    if (N % 2 == 0) {
        return false;
    }

    return std::vector<int>(N, 0);
}