#P12592. [集训队互测 2023day2]nth(没配置好)

    ID: 11754 通信题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>数据结构队列字符串CF3000构造分治二分数学

[集训队互测 2023day2]nth(没配置好)

题目描述

Eve 有一个大小为 SS 的非负整数多重集合,所有元素均小于 M=221M=2^{21}。她把元素分给 Alice 和 Bob,分别得到集合 AA 和 BB。每个数在同一方的集合中至多出现一次,但可以同时出现在两方,因此求第 cc 小时要把这两次出现都算进去。

两人各自知道自己的集合、SS 和 cc。他们可以互相发送比特,最终由任意一方向 Eve 报告合并后的第 cc 小元素。请尽量减少两人发送的比特总数。保证 1≤c≤S1\le c\le S。

实现接口

使用 C++11 或更高版本,提交一个包含 nth.h 的源文件。头文件负责程序入口和通信。请将实现和自定义变量放在 Alice、Bob 两个命名空间内,两方只能通过题给接口交换信息。

Alice 的接口如下:

namespace Alice {
    void initA(std::bitset<M> A, unsigned S, unsigned c);
    void receiveA(bool x);
    void sendA(bool x);
}

实现 initA 和 receiveA。initA 中的 A[i] 表示整数 ii 是否属于 Alice。receiveA(x) 表示收到 Bob 发来的一个比特。sendA(x) 将一个比特加入发给 Bob 的队列,由评测库提供。

Bob 对应实现 initB(std::bitset<M> B, unsigned S, unsigned c) 和 receiveB(bool x),使用 sendB(bool x) 发送信息。两方都可以调用 report(unsigned ans);调用后本次测试结束。

初始化时分别调用两方的初始化函数,顺序可以任意。之后,只要有消息可投递,评测库就取某个非空队列的队首比特,调用接收方的函数。每个队列内部保持发送顺序。两方程序分别运行,应能在任何符合规则的投递顺序下报告正确答案。

样例与本地测试

可以下载 完整样例输入 和 [本地测试程序](file://sample_grader.cpp)。本地编译命令如下:

g++ -std=c++11 -O2 -DNTH_LOCAL_GRADER solution.cpp sample_grader.cpp -o nth

本地测试输入的前两行是长度为 MM 的二进制字符串。第 i+1i+1 位为 1 表示该方收到整数 ii。第三行是 cc。本地测试程序输出期望答案、实际答案和通信比特总数。

样例中 A={1,2,3,7,8}A=\{1,2,3,7,8\},B={2,4,6}B=\{2,4,6\},c=4c=4。合并排序后为 (1,2,2,3,4,6,7,8)(1,2,2,3,4,6,7,8),因此应报告 33。

评分方式

任一测试点答错、未报告答案或发送量超过 2212^{21} 比特,整题得 00 分。全部答对时,令 bb 为所有测试点中最大的通信比特数。对下表中的每个阈值 LL,若 b≤Lb\le L,就加上该阈值对应的分数。

阈值 LL 每个满足的阈值加分
2i2^i,i=11,13,15,17,19,21i=11,13,15,17,19,21 3
100i100i,i=2,3,…,10i=2,3,\ldots,10
10i10i,i=9,10,…,19i=9,10,\ldots,19 5

总分为 100100 分。全部测试点的通信量都不超过 9090 比特时可获满分。