#P12592. [集训队互测 2023day2]nth(没配置好)
[集训队互测 2023day2]nth(没配置好)
题目描述
Eve 有一个大小为 的非负整数多重集合,所有元素均小于 。她把元素分给 Alice 和 Bob,分别得到集合 和 。每个数在同一方的集合中至多出现一次,但可以同时出现在两方,因此求第 小时要把这两次出现都算进去。
两人各自知道自己的集合、 和 。他们可以互相发送比特,最终由任意一方向 Eve 报告合并后的第 小元素。请尽量减少两人发送的比特总数。保证 。
实现接口
使用 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] 表示整数 是否属于 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
本地测试输入的前两行是长度为 的二进制字符串。第 位为 1 表示该方收到整数 。第三行是 。本地测试程序输出期望答案、实际答案和通信比特总数。
样例中 ,,。合并排序后为 ,因此应报告 。
评分方式
任一测试点答错、未报告答案或发送量超过 比特,整题得 分。全部答对时,令 为所有测试点中最大的通信比特数。对下表中的每个阈值 ,若 ,就加上该阈值对应的分数。
| 阈值 | 每个满足的阈值加分 |
|---|---|
| , | 3 |
| , | |
| , | 5 |
总分为 分。全部测试点的通信量都不超过 比特时可获满分。