#1694. 会议

    ID: 1694 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>CTT赛事:contest1047来源:qoj.ac数据:公开样例

会议

会议

题目描述

标题: 会议 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

这是一道交互题。

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

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

  • 自反性:∀a∈D,都有 a=a。
  • 传递性:∀a,b,c∈D,若 a=b,且 b=c,则 a=c。
  • 对称性:∀a,b∈D,若 a=b,则 b=a。

集合 D 中定义了全序关系 ≤,满足:

  • 完全性:∀a,b∈D,有 a≤b 或 b≤a。
  • 传递性:∀a,b,c∈D,若 a≤b 且 b≤c,则 a≤c。
  • 反对称性:∀a,b∈D,若 a≤b 且 b≤a,则 a=b。

全序关系 ≤ 所关联的严格全序关系 < 满足:

  • ∀a,b∈D,a<b 当且仅当 a≤b 且 a≠b。

定义由 D 中的元素所构成的可重集合 S 的严格众数为一个元素 x,使得 x 在可重集合 S 中出现的次数严格超过集合大小的一半。即,x 为严格众数当且仅当:

∑e∈S[e=x]>12|S|

你需要在线维护一个由 D 中的元素构成的可重集合 S(初始时 S 为空集 ∅),支持以下操作:

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

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

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

  • 等价测试 E:给出元素 x,y∈D,交互库返回 x=y 是否成立。
  • 偏序测试 C:给出元素 x,y∈D,交互库返回 x≤y 是否成立。

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

实现细节

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

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

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

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

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


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

对于两个类型为 D_t 中的变量 x 与 y(设其对应 x,y∈D),x <= y 将返回一个 bool 类型的变量,当 x≤y 时,其返回为 true,否则返回为 false。

调用运算符 <= 将造成 1 单位的 C-代价。


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

对于两个类型为 D_t 中的变量 x 与 y(设其对应 x,y∈D),x == y 将返回一个 bool 类型的变量,当 x=y 时,其返回为 true,否则返回为 false。

调用运算符 == 将造成 1 单位的 E-代价。


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

  • a > b 等价于 !(a <= b)。调用该运算符将造成 1 单位的 C-代价。
  • a < b 等价于 !(b <= a)。调用该运算符将造成 1 单位的 C-代价。
  • a >= b 等价于 b <= a。调用该运算符将造成 1 单位的 C-代价。
  • a != b 等价于 !(a == b)。调用该运算符将造成 1 单位的 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 行,每行两个整数 op x,描述一个操作:

  • 当 op=0 时,表示进行一次插入操作,插入的元素为 x。
  • 当 op=1 时,表示进行一次删除操作,删除的元素为在第 x 次操作时所插入的元素。

保证 op∈{0,1},0≤x≤105。需要注意的是,在读入插入操作的数据时,每个 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 ≤100 A 2 2 ≤5000 6 3 ≤50000 18 4 ≤105 B 74

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

  • 记 C 表示在每组询问中,你所造成的 C-代价 的最大值。

  • 记 E 表示在每组询问中,你所造成的 E-代价 的最大值。

  • 若 max(C,E)≥1000,则无论何种评分方式,你的得分均为 0 分。

  • 评分方式 A:

    • 若对于每次调用,你所回答绝对众数的存在性正确,则可得到 50% 的分数。
    • 若对于每次调用,你给出了可能的候选解,则可得到 50% 的分数。
    • 你的最终得分为上述两部分得分之和。
    • 交互库保证,在任意可能取得分数(必满足 max(C,E)≤1000)的交互过程中,交互库所占用的时间不超过 200 毫秒,空间不超过 16 MB。
  • 评分方式 B:

    • 设评分参数 p∈(0,1)。

      • 若对于每次调用,你所回答绝对众数的存在性正确,且给出了可能的候选解,则 p=100%。
      • 若对于每次调用,你所回答绝对众数的存在性正确,则 p=10%。
      • 若对于每次调用,你给出了可能的候选解,则 p=10%。
      • 否则,p=0。
    • 若 C>500,则你的得分为 4⋅p。

    • 否则,若 C>20,则你的得分为 9⋅p。

    • 否则,若 C>0,则你的得分为 15⋅p。

    • 否则,若 E>800,则你的得分为 18⋅p。

    • 否则,若 E>100,则你的得分为 (20+2×800−E100)⋅p。

    • 否则,若 E>10,则你的得分为 (35+2×100−E10)⋅p。

    • 否则,若 E>5,则你的得分为 (64−E)⋅p。

    • 否则,若 E=5,则你的得分为 60⋅p 分。

    • 否则,若 E=4,则你的得分为 64⋅p 分。

    • 否则,若 E=3,则你的得分为 69⋅p 分。

    • 否则,你的得分为 74⋅p 分。

  • 你所回答绝对众数的存在性正确 指:

    • 当绝对众数存在时,你返回的值为 true。
    • 当绝对众数不存在时,你返回的值为 false。
    • 是否调用了 submit,或报告的解是否正确,均不会造成影响,你可以任意提交,或不提交任何的解。
  • 你给出了可能的候选解 指:

    • 当绝对众数存在时,你调用了恰好一次 submit,且报告的解恰为唯一的绝对众数。
    • 当绝对众数不存在时,是否调用 submit、提供了一组怎样的解均不受影响。
    • 函数返回的值不会造成影响,你可以返回任意 true 或 false。

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

提示

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

int subtask_id();
g++ majority.cpp grader_majority.cpp -o majority -O2 -std=c++14

样例 2

5
0 1
0 1
0 2
0 2
1 2
1 1
1 1
1 1
0 -1
1 2