QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 2048 MB Total points: 100 Interactive
统计

这是一道交互题。

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

集合 $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 中的变量 xy(设其对应 $x, y \in D$),x <= y 将返回一个 bool 类型的变量,当 $x \le y$ 时,其返回为 true,否则返回为 false

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


  • 运算符 == 描述了二元关系 $=$,其接口信息如下:
bool operator== (const D_t &rhs) const;

对于两个类型为 D_t 中的变量 xy(设其对应 $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();

请注意,在【子任务】部分,包含了本题的评分方式。特别地,如果你在 inserterase 的调用中:

  • 返回了绝对众数的存在性,但是在 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

考虑以下输入:

5
0 1
0 1
0 2
0 2
1 2

一组期望的输出如下:

1 1
1 1
1 1
0 -1
1 2

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

样例 2

考虑以下输入:

13
0 1
0 2
0 3
0 1
0 1
1 4
1 5
0 2
0 2
1 6
1 7
0 3
0 3

一组期望的输出如下:

1 1
0 -1
0 -1
0 -1
1 1
0 -1
0 -1
0 -1
1 2
0 -1
0 -1
0 -1
1 3

子任务

记 $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、提供了一组怎样的解均不受影响。
    • 函数返回的值不会造成影响,你可以返回任意 truefalse

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

提示

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