#BT10. 双人名次查询

双人名次查询

双人名次查询

Alice 和 Bob 各保存一份长度为 nn 的非降整数序列,分别记为 AA 和 BB。将两个序列的所有元素合在一起,重复值分别保留,求从小到大排列后的第 kk 个数。

你提交的一份程序会同时启动两次,分别扮演 Alice 和 Bob。两份程序各自只能读到自己的序列,可以通过评测管理器传递少量整数,共同求出答案。

启动与初始输入

评测器会将角色编号作为命令行参数传入。C++ 程序可通过 argv[1] 读取:0 表示 Alice,1 表示 Bob。两份程序运行在彼此隔离的环境中。

每份程序首先从标准输入读取两行:

n k Q
c_1 c_2 ... c_n

其中 Q=100Q=100。Alice 读到的 cc 是 AA,Bob 读到的 cc 是 BB。

通信协议

Alice 发起每一轮通信。

  1. Alice 输出 S x,其中 −1≤x≤109+1-1\le x\le 10^9+1。管理器把同一行发送给 Bob。
  2. Bob 读到这一行后,输出 S y,取值范围相同。管理器把同一行发送给 Alice。
  3. Alice 读到回复后,可以发起下一轮通信,也可以输出最终答案。

每条 S 消息只携带一个整数。两份程序发送的 S 消息总数至多为 Q=100Q=100,即至多进行 50 轮往返。整数的含义由两份程序自行约定。

Alice 最后输出 ! v,声明第 kk 小的数为 vv,随后正常退出。最终答案不计入消息数。管理器会向 Bob 发送 F v,Bob 收到 F 后正常退出。

每条消息独占一行,输出后刷新缓冲区。例如使用 cout << "S " << x << endl;。若输入结束,或收到 F -1,程序正常退出。

评测管理器只转发符合协议的消息,并检查最终答案与通信量。发送消息、等待回复的顺序由上述协议确定。

数据范围

  • 1≤n≤1051\le n\le 10^5;
  • 1≤k≤2n1\le k\le 2n;
  • 0≤Ai,Bi≤1090\le A_i,B_i\le 10^9;
  • AA 和 BB 分别非降。

通信示例 1

本例的私有数据为 A=[1,4,8]A=[1,4,8]、B=[2,5,9]B=[2,5,9],k=4k=4,正确答案为 55。

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,第二行为 AA,第三行为 BB。 编译管理器和选手程序后,可运行:

python local_runner.py --manager ./manager --solution ./solution --case sample.in