会议 - Problem

这是一道交互题。

本来这里应该有一个非常美妙的题面，但是很抱歉，题面已经鸽没了。

集合 $D$ 中定义了等价关系 $=$ 满足：

自反性：$\forall a \in D$，都有 $a = a$。
传递性：$\forall a, b, c \in D$，若 $a = b$，且 $b = c$，则 $a = c$。
对称性：$\forall a, b \in D$，若 $a = b$，则 $b = a$。

集合 $D$ 中定义了全序关系 $\leq$，满足：

完全性：$\forall a, b \in D$，有 $a \le b$ 或 $b \le a$。
传递性：$\forall a, b, c \in D$，若 $a \le b$ 且 $b \le c$，则 $a \le c$。
反对称性：$\forall a, b \in D$，若 $a \le b$ 且 $b \le a$，则 $a = b$。

全序关系 $\leq$ 所关联的严格全序关系 $<$ 满足：

$\forall a, b \in D$，$a < b$ 当且仅当 $a \leq b$ 且 $a \ne b$。

定义由 $D$ 中的元素所构成的可重集合 $S$ 的严格众数为一个元素 $x$，使得 $x$ 在可重集合 $S$ 中出现的次数严格超过集合大小的一半。即，$x$ 为严格众数当且仅当： $$\displaystyle \sum_{e \in S} [e = x] > \frac{1}{2}|S|$$

你需要在线维护一个由 $D$ 中的元素构成的可重集合 $S$（初始时 $S$ 为空集 $\varnothing$），支持以下操作：

插入：给定元素 $x \in D$，在可重集合 $S$ 中加入元素 $x$。
删除：给定元素 $x \in D$，在可重集合 $S$ 中删除元素 $x$。保证元素 $x \in S$。特别地，若 $x$ 在 $S$ 中出现了多次，则你只需要删除恰好一次。

在每次操作后，你需要报告集合 $S$ 中是否存在绝对众数。若存在，你还需要给出 $S$ 中的绝对众数。

你可以向交互库进行若干次询问，每次询问可形如：

等价测试 $\mathbf{E}$：给出元素 $x, y \in D$，交互库返回 $x = y$ 是否成立。
偏序测试 $\mathbf{C}$：给出元素 $x, y \in D$，交互库返回 $x \le y$ 是否成立。

每个子任务中对每种测试的数量进行了限制。你的得分将取决于你的回答的正确性，以及你在每次操作后，进行每种询问的数量。

实现细节

这是一道交互题，本题仅支持 C++ 语言。

你不需要，也不应该实现 main() 函数，从标准输入输出或任何文件中读取或写入任何数据。

你需要包含头文件 majority.h。

在头文件中，定义了数据类型 D_t，其描述了 $D$ 中的元素。

交互库为 D_t 重载了以下运算符，描述了上文中所包含的二元关系：

运算符 <= 描述了二元关系 $\le$，其接口信息如下:

bool operator<= (const D_t &rhs) const;

对于两个类型为 D_t 中的变量 x 与 y（设其对应 $x, y \in D$），x <= y 将返回一个 bool 类型的变量，当 $x \le y$ 时，其返回为 true，否则返回为 false。

调用运算符 <= 将造成 $1$ 单位的 $\mathbf{C}$-代价。

运算符 == 描述了二元关系 $=$，其接口信息如下:

bool operator== (const D_t &rhs) const;

对于两个类型为 D_t 中的变量 x 与 y（设其对应 $x, y \in D$），x == y 将返回一个 bool 类型的变量，当 $x = y$ 时，其返回为 true，否则返回为 false。

调用运算符 == 将造成 $1$ 单位的 $\mathbf{E}$-代价。

此外，为了解题的方便，我们额外重载了运算符 >、>=、!=、<，其定义如下：

a > b 等价于 !(a <= b)。调用该运算符将造成 $1$ 单位的 $\mathbf{C}$-代价。
a < b 等价于 !(b <= a)。调用该运算符将造成 $1$ 单位的 $\mathbf{C}$-代价。
a >= b 等价于 b <= a。调用该运算符将造成 $1$ 单位的 $\mathbf{C}$-代价。
a != b 等价于 !(a == b)。调用该运算符将造成 $1$ 单位的 $\mathbf{E}$-代价。

为了方便你的调试，我们还提供了函数 get_value()。调用该函数，将返回类 D_t 中的成员变量 info。该方法仅包含在样例交互库中，用于方便你来调试你的算法。在评测时，你不可以通过任何手段得到变量 info 的值，否则将会被视为攻击交互库，所得分数无效。

你需要实现以下函数：

bool insert(const D_t& x);

其描述交互库发起了一次插入操作。
你需要返回一个 bool 类型的变量，表示在操作完成后集合是否存在绝对众数。
特别地，若返回的值为 true，则你需要调用 submit 函数来提交绝对众数，具体详见下文中 submit 函数的介绍。

bool erase(int id);

其描述交互库发起了一次删除操作。
- 变量 id 表示本次删除的元素是第 id 次插入操作所插入的元素。
- 保证第 id 次插入操作所插入的元素在此前没有被删除过。
你需要返回一个 bool 类型的变量，表示在操作完成后集合是否存在绝对众数。
特别地，若返回的值为 true，则你需要调用 submit 函数来提交绝对众数，具体详见下文中 submit 函数的介绍。

特别地，交互库提供了 submit 函数，用于提交答案：

void submit(const D_t& x);

当操作后集合存在绝对众数时，你需要调用该函数恰好一次，其中参数 x 表示 $S$ 中的绝对众数。
当操作后集合不存在绝对众数时，你不应该调用该函数。

而函数 subtask_id() 则返回了该测试点的子任务编号。特别地，在样例交互库中，该函数将总是返回 $0$。

int subtask_id();

请注意，在【子任务】部分，包含了本题的评分方式。特别地，如果你在 insert 与 erase 的调用中：

返回了绝对众数的存在性，但是在 submit 时没有进行提交，或者提交了错误的答案。
给出了可能的解，但是对存在性的判断并不正确。

那么你将获得一部分的分数。

样例交互库

在本题的下发文件中，包含了样例交互库 grader_majority.cpp，你可以通过该交互库来帮助你编写程序。

需要注意的是，在实际测试时，所使用的交互库与该样例交互库有所不同，选手不应依赖该交互库的实现。

你可以在终端中使用以下命令，将你的程序 majority.cpp 编译为可执行文件 majority：

g++ majority.cpp grader_majority.cpp -o majority -O2 -std=c++14

需要注意的是，在最终测试时，所使用的交互库的实现与样例交互库有所不同。选手不应该依赖样例交互库的实现。

输入格式

样例交互库将从标准输入中按照以下格式读取输入数据：

输入的第一行包含一个整数 $Q$，表示询问的数量。

接下来 $Q$ 行，每行两个整数 $\mathrm{op}~ x$，描述一个操作：

当 $\mathrm{op} = 0$ 时，表示进行一次插入操作，插入的元素为 $x$。
当 $\mathrm{op} = 1$ 时，表示进行一次删除操作，删除的元素为在第 $x$ 次操作时所插入的元素。

保证 $\mathrm{op} \in \{0, 1\}$，$0 \le x \le 10^5$。需要注意的是，在读入插入操作的数据时，每个 D_t 类型的变量将使用一个非负整数表示。构造函数 D_t(x) 可以将 $32$ 位无符号整数 x 转换为对应的 D_t 类型的变量。

输出格式

样例交互库将从标准输出中按照以下输出格式进行输出：

输出的第一行包含了你的交互过程的信息。
接下来 $Q$ 行，每行包含两个整数。
- 第一个整数为 $\{ 0, 1 \}$ 中的整数，表示你在调用中返回的值。其中 $0$ 表示 false，$1$ 表示 true。
- 第二个整数为你所提交的答案所对应的 info 的值。特别地，若你在这轮操作后没有提交任何答案，则其值为 $-1$。

样例数据

样例 1

考虑以下输入：

一组期望的输出如下：

请注意，1 操作的参数 $x$ 的含义为删除第 $x$ 次插入操作所插入的元素，而不是删除元素 $x$。

样例 2

考虑以下输入：

一组期望的输出如下：

子任务

记 $Q$ 表示一个测试点中所进行的询问的数量。

子任务编号	$Q$	评分方式	分值
$1$	$\le 100$	A	$2$
$2$	$\le 5\,000$		$6$
$3$	$\le 50\,000$		$18$
$4$	$\le 10^5$	B	$74$

以下是评分方式的相关解释：

记 $C$ 表示在每组询问中，你所造成的 $\mathbf{C}$-代价的最大值。
记 $E$ 表示在每组询问中，你所造成的 $\mathbf{E}$-代价的最大值。
若 $\max(C, E) \ge 1000$，则无论何种评分方式，你的得分均为 $0$ 分。
评分方式 A：
- 若对于每次调用，你所回答绝对众数的存在性正确，则可得到 $50\%$ 的分数。
- 若对于每次调用，你给出了可能的候选解，则可得到 $50\%$ 的分数。
- 你的最终得分为上述两部分得分之和。
- 交互库保证，在任意可能取得分数（必满足 $\max(C, E) \le 1\,000$）的交互过程中，交互库所占用的时间不超过 $200$ 毫秒，空间不超过 $16$ MB。
评分方式 B：
- 设评分参数 $p \in (0, 1)$。
  - 若对于每次调用，你所回答绝对众数的存在性正确，且给出了可能的候选解，则 $p = 100\%$。
  - 若对于每次调用，你所回答绝对众数的存在性正确，则 $p = 10\%$。
  - 若对于每次调用，你给出了可能的候选解，则 $p = 10\%$。
  - 否则，$p = 0$。
- 若 $C > 500$，则你的得分为 $4 \cdot p$。
- 否则，若 $C > 20$，则你的得分为 $9 \cdot p$。
- 否则，若 $C > 0$，则你的得分为 $15 \cdot p$。
- 否则，若 $E > 800$，则你的得分为 $18 \cdot p$。
- 否则，若 $E > 100$，则你的得分为 $\displaystyle \left(20 + 2 \times \frac{800-E}{100}\right) \cdot p$。
- 否则，若 $E > 10$，则你的得分为 $\displaystyle \left(35 + 2 \times \frac{100-E}{10}\right) \cdot p$。
- 否则，若 $E > 5$，则你的得分为 $(64 - E) \cdot p$。
- 否则，若 $E = 5$，则你的得分为 $60 \cdot p$ 分。
- 否则，若 $E = 4$，则你的得分为 $64 \cdot p$ 分。
- 否则，若 $E = 3$，则你的得分为 $69 \cdot p$ 分。
- 否则，你的得分为 $74 \cdot p$ 分。
你所回答绝对众数的存在性正确 指：
- 当绝对众数存在时，你返回的值为 true。
- 当绝对众数不存在时，你返回的值为 false。
- 是否调用了 submit，或报告的解是否正确，均不会造成影响，你可以任意提交，或不提交任何的解。
你给出了可能的候选解 指：
- 当绝对众数存在时，你调用了恰好一次 submit，且报告的解恰为唯一的绝对众数。
- 当绝对众数不存在时，是否调用 submit、提供了一组怎样的解均不受影响。
- 函数返回的值不会造成影响，你可以返回任意 true 或 false。

即，当你完整正确地回答了所有询问，且满足 $E \le \mathbf{2}$ 且 $C = \mathbf{0}$ 时，你可以得到满分。

提示

由于输入数据保证了 $0 \le x \le 10^5$，因此你可以使用 D_t(-1)、D_t(-2)、…… 来生成出与所有插入的元素均不相等的对象。

QOJ.ac

QOJ

#5093. 会议