luogu#P8494. [IOI2022] 最罕见的昆虫

[IOI2022] 最罕见的昆虫

题目背景

滥用评测资源者封号

本题为交互题。

不需要也不应该在提交的程序中包含 insects.h 头文件和主函数。

但是在您的程序中,需要声明以下三个函数:

void move_inside(int i);
void move_outside(int i);
int press_button();

例如,您的程序可以是这样:

#include <bits/stdc++.h>
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 的房子四周有 NN 只昆虫,编号为 00N1N-1。每只昆虫有一个类型,以从 0010910^9(包含 0010910^9)的整数编号。可能有多只昆虫类型相同。

假设将昆虫按照类型分组。我们定义最常见昆虫类型的基数是昆虫最多的分组中的昆虫数。类似地,最罕见昆虫类型的基数是昆虫最少的分组中的昆虫数。

例如,假设有 1111 只昆虫,类型分别为 [5,7,9,11,11,5,0,11,9,100,9][5, 7, 9, 11, 11, 5, 0, 11, 9, 100, 9]。在此情形中,最常见昆虫类型的基数是 33,是因为类型 99 和类型 1111 的分组均有最多数目的昆虫,每个分组都有 33 只。最罕见昆虫类型的基数是 11,是因为类型 77、类型 00 和类型 100100 的分组均有最少数目的昆虫,每个分组都有 11 只。

Pak Blangkon 不知道这些昆虫的类型。他有一台单按钮的机器,可以提供昆虫类型相关的信息。刚开始时,机器是空的。在使用机器时,可以做如下三种操作:

  1. 将一只昆虫放进机器。
  2. 将一只昆虫取出机器。
  3. 按下机器的按钮。

每种操作最多可以做 40  00040\;000 次。

每当按下按钮时,机器会报告在机器内的最常见昆虫类型的基数。

你的任务是使用上述机器,确定 Pak Blangkon 的房子四周所有 NN 只昆虫中最罕见昆虫类型的基数。此外,在某些子任务里,你的得分取决于机器执行某种操作的最大次数(详见子任务一节)。

输入格式

你要实现以下函数:

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

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

void move_inside(int i)
  • ii:将被放进机器的昆虫编号。编号 ii 的取值范围是 00N1N-1(包含 00N1N-1)。
  • 如果昆虫已在机器内,函数调用不会影响机器内昆虫的集合。但是,调用仍会被计入此类操作的次数。
  • 此函数最多可以被调用 40  00040\;000 次。
void move_outside(int i)
  • ii:将被从机器中取出的昆虫编号。编号 ii 的取值范围是 00N1N-1(包含 00N1N-1)。
  • 如果昆虫已在机器外,函数调用不会影响机器内昆虫的集合。但是,调用仍会被计入此类操作的次数。
  • 此函数最多可以被调用 40  00040\;000 次。
int press_button()
  • 此函数返回机器内最常见昆虫类型的基数。
  • 此函数最多可以被调用 40  00040\;000 次。
  • 评测程序不是适应性的。也就是说,所有 NN 只昆虫的类型在 min_cardinality 调用前已经确定。

输出格式

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

min_cardinality(6)

此函数按以下次序调用了 move_insidemove_outsidepress_button

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

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

在这个例子里,move_inside 被调用 77 次,move_outside 被调用 11 次,press_button 被调用 66 次。

提示

约束条件

  • 2N20002 \le N \le 2000

子任务

  1. (10 分) N200N \le 200
  2. (15 分) N1000N \le 1000
  3. (75 分) 没有额外的约束条件。

如果在某个测试用例上,函数 move_insidemove_outsidepress_button 的调用次数不符合“实现细节”中给出的约束条件,或者 min_cardinality 的返回值不正确,你的解答在此子任务上得分为 00

qq 为以下三个值的 最大值move_inside 的调用次数、move_outside 的调用次数、press_button 的调用次数。

在子任务 3 中,你可能会得部分分。令 mm 为此子任务所有测试用例的 qN\frac{q}{N} 的最大值。你在此子任务的得分将根据以下表格计算:

条件 得分
20<m20 \lt m 00 (CMS 报告“Output isn’t correct”)
6<m206 \lt m \le 20 225m2\frac{225}{m - 2}
3<m63 \lt m \le 6 8123m281 - \frac{2}{3} m^2
m3m \le 3 7575

评测程序示例

TT 是长度为 NN 的整数数组,其中 T[i]T[i] 是编号为 ii 的昆虫的类型。

评测程序示例按以下格式读取输入:

  • 11 行:NN
  • 22 行:T[0]  T[1]    T[N1]T[0] \; T[1] \; \ldots \; T[N - 1]

如果评测程序示例检测到非法行为,评测程序示例将输出 Protocol Violation: <MSG>,其中 <MSG> 为如下某种类型:

  • invalid parameter:在函数调用 move_insidemove_outside 时,参数 ii 的值不在 00N1N-1 的范围内(包括 00N1N-1)。
  • too many calls:函数 move_insidemove_outsidepress_button某个的调用次数超过 40  00040\;000 次。

否则,评测程序示例按以下格式输出:

  • 11 行:min_cardinality 的返回值;
  • 22 行:qq

约定

题面在给出函数接口时,会使用一般性的类型名称 voidboolintint[](数组)和 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);
}