#BT10. 双人名次查询
双人名次查询
双人名次查询
Alice 和 Bob 各保存一份长度为 的非降整数序列,分别记为 和 。将两个序列的所有元素合在一起,重复值分别保留,求从小到大排列后的第 个数。
你提交的一份程序会同时启动两次,分别扮演 Alice 和 Bob。两份程序各自只能读到自己的序列,可以通过评测管理器传递少量整数,共同求出答案。
启动与初始输入
评测器会将角色编号作为命令行参数传入。C++ 程序可通过 argv[1] 读取:0 表示 Alice,1 表示 Bob。两份程序运行在彼此隔离的环境中。
每份程序首先从标准输入读取两行:
n k Q
c_1 c_2 ... c_n
其中 。Alice 读到的 是 ,Bob 读到的 是 。
通信协议
Alice 发起每一轮通信。
- Alice 输出
S x,其中 。管理器把同一行发送给 Bob。 - Bob 读到这一行后,输出
S y,取值范围相同。管理器把同一行发送给 Alice。 - Alice 读到回复后,可以发起下一轮通信,也可以输出最终答案。
每条 S 消息只携带一个整数。两份程序发送的 S 消息总数至多为 ,即至多进行 50 轮往返。整数的含义由两份程序自行约定。
Alice 最后输出 ! v,声明第 小的数为 ,随后正常退出。最终答案不计入消息数。管理器会向 Bob 发送 F v,Bob 收到 F 后正常退出。
每条消息独占一行,输出后刷新缓冲区。例如使用 cout << "S " << x << endl;。若输入结束,或收到 F -1,程序正常退出。
评测管理器只转发符合协议的消息,并检查最终答案与通信量。发送消息、等待回复的顺序由上述协议确定。
数据范围
- ;
- ;
- ;
- 和 分别非降。
通信示例 1
本例的私有数据为 、,,正确答案为 。
Alice 初始读到:
3 4 100
1 4 8
Bob 初始读到:
3 4 100
2 5 9
双方可以约定 Alice 发送下标、Bob 返回该下标的元素。以下是一段合法通信:
| Alice 输出 | Bob 收到 | Bob 输出 | Alice 收到 |
|---|---|---|---|
S 2 |
S 5 |
||
S 3 |
S 9 |
||
! 5 |
F 5 |
正常退出 | |
这段通信共发送 4 条 S 消息。
通信示例 2
Alice 初始读到 1 2 100 和序列 [7];Bob 初始读到相同的首行和序列 [7]。合并后的序列为 [7,7],第 2 小为 7。
Alice 发送 S 1,Bob 回复 S 7,Alice 输出 ! 7,Bob 随后收到 F 7。这段通信共发送 2 条 S 消息。
本地调试
C++17 通信模板、本地转发器、本地管理器源码、样例 1 私有输入、样例 2 私有输入。 模板实现了上述“下标/元素”约定下的 Bob,Alice 部分留作实现。
本地私有输入的格式是:
第一行 n k,第二行为 ,第三行为 。
编译管理器和选手程序后,可运行:
python local_runner.py --manager ./manager --solution ./solution --case sample.in
相关
在下列比赛中: