题面更新: 禁止在已定义的两个命名空间 Alice 和 Bob 外定义任何变量或函数.
Alice 和 Bob 正在与 Eve 玩一个游戏. Eve 有一个非负整数集(可重) $S$, 且所有数均小于 $M=2^{21}$, 他将这个集合分为两部分 $A$ 和 $B$, 并分别告诉了 Alice 和 Bob. 为了信息传输的方便, 他保证了每种数在一个部分内至多出现一次. 他给了 Alice 和 Bob 一个任务: 求出 $S$ 中第 $c$ 小的数. 但这过于简单, 因此 Eve 要求他们只能传输很少 bit 的信息.
实现细节
本题只支持 C++ 11 及以上.
在文件开头需要含有语句 #include "nth.h".
在命名空间 Alice 内, 你需要实现:
void initA(std::bitset<M> A, unsigned S,unsigned c), A 描述了给 Alice 的集合: 第 $i$ 位是 $1$ 当且仅当 $i$ 在集合内; $S$ 为 Eve 的集合的大小(同一种数出现多次会对该值贡献多次); $c$ 的含义见题目描述.
void receiveA(bool x), 表示 Alice 接收到 Bob 的 1 bit 信息: 信息的值即为 $x$.
你可以调用: void sendA(bool x) 表示向 Bob 发送信息 $x$.
类似的, 在命名空间 Bob 内, 你需要实现 initB 和 receiveB, 并可以调用 sendB.
在两个命名空间内, 你均可以调用函数 void report(unsigned ans), 表示 Alice 和 Bob 之一向 Eve 报告答案.
注意:
- 你不需要也不应该定义或声明 main 函数.
- 你可以在命名空间内部定义全局变量, 但任何在两个命名空间间通过变量或地址等交流行为将被视为作弊.
- 禁止在已定义的两个命名空间 Alice 和 Bob 外定义任何变量或函数.
测试程序
在测试程序中, 对于每个测试点: 首先会以任意顺序调用 initA 和 initB 各一次. 程序维护两个队列, 表示一人发送给另一人但未被接受的消息, 调用 send 时只会将信息存入对应队列. 测试程序会不断选出任意一个非空队列, 取出队首信息并调用对应 receive 函数. 在 report 被调用时, 其会检查答案并退出程序.
通过联合编译你的程序和 sample_grader.cpp 可得到可执行文件.
该程序从标准输入读入两行长为 $M$ 的 $0/1$ 字符串和一个整数.
- 第一行的第 $i+1$ 个字符为 $1$ 当且仅当 Alice 接受的集合中有 $i$.
- 第二行的第 $i+1$ 个字符为 $1$ 当且仅当 Bob 接受的集合中有 $i$.
- 第三行表示 $c$.
程序向标准输出写出一行三个数, 分别表示期望答案, 实际答案和信息传输 bit 量(即 sendA 和 sendB 调用的总次数).
样例数据
样例输入
0111000110...
0010101000...
4其中 ... 代表 $M-10$ 个 $0$ (包内有完整样例).
则 Alice 的集合为 $\{1,2,3,7,8\}$, Bob 的集合为 $\{2,4,6\}$, Eve 的集合为 $\{1,2,2,3,4,6,7,8\}$, 其中第 $4$ 小的数是 $3$.
数据范围与评分方式
$1≤c≤S$.
若在某个测试点中返回了错误答案, 则本题获得 $0$ 分.
若对于所有测试点均返回正确答案:
- 对每个 $L=2^i$,$i∈\{11,13,15,17,19,21\}$, 若所有测试点通讯位数不超过 $L$ 则获得 $3$ 分.
- 对每个 $L=100i$,$i∈\{2,3,4,5,6,7,8,9,10\}$, 若所有测试点通讯位数不超过 $L$ 则获得 $3$ 分.
- 对每个 $L=10i$,$i∈\{9,10,11,12,13,14,15,16,17,18,19\}$, 若所有测试点通讯位数不超过 $L$ 则获得 $5$ 分.
保证交互库处理不超过 $2097152$ 次通讯时运行时间不超过 50ms, 空间不超过 6MB.
注
虽然 QOJ 支持对通信式题目的评测，但为了保留原实现方式，在这里不做任何修改。请不要攻击交互库。