P12575 [UOI 2021] 第 k 小的数

这是一道交互题。 哥萨克·武斯有三个秘密的正整数数组 $a$、$b$ 和 $c$。它们的长度分别为 $|a|$、$|b|$ 和 $|c|$，这些长度不一定相同。已知每个数组都是已排序的，即每个后续元素都不小于前一个元素。 你想获取关于这些数组的特定信息——即在三个数组合并后的排序数组中第 $k$ 小的元素值。也就是说，如果将这三个数组合并成一个长度为 $|a|+|b|+|c|$ 的大数组并从小到大排序，你需要找出排序后数组中的第 $k$ 个元素。 哥萨克·武斯拒绝直接展示这些数组给你。但他同意以下交互方式：你可以查询特定数组中的特定位置的元素值。你可以选择一个数组和一个位置，哥萨克会告诉你该位置上的元素值。注意，你可以多次进行这种查询操作，且不限于同一个数组。由于哥萨克非常忙碌，他最多允许你提出 $Q$ 次查询。 你的任务是找出三个数组合并后第 $k$ 小的元素。

第一行包含五个整数 $|a|$、$|b|$、$|c|$、$k$ 和 $g$（$0 \leq |a|, |b|, |c| \leq 10^6$，$1 \leq k \leq |a| + |b| + |c|$）。 保证所有数组中的元素都在 $[1, 10^9]$ 范围内。 整数 $g$（$0 \leq g \leq 9$）表示测试用例的分组编号（参见评分标准）。 ### 交互方式 首先读取五个整数 $|a|$、$|b|$、$|c|$、$k$ 和 $g$。 要发起查询，输出 `1 r m`。其中： - $r$ 表示数组编号（$1$ 对应数组 $a$，$2$ 对应数组 $b$，$3$ 对应数组 $c$）； - $m$ 表示该数组中的位置（例如，$m=1$ 表示第一个元素，$m=|a|$ 表示最后一个元素）。 示例查询 `1 3 10` 表示获取数组 $c$ 的第 $10$ 个元素。 每次查询后，必须换行并刷新输出缓冲区，否则会得到 "超出时间限制" 的判定。刷新缓冲区的方法： - C++: `fflush(stdout)` 或 `cout.flush()`； - Java: `System.out.flush()`； - Pascal: `flush(output)`； - Python: `stdout.flush()`； 其他语言请参考相关文档。 注意：如果查询无效（超出查询限制或不满足约束条件），交互器会输出 `-1` 并终止程序。如果读取到 `-1`，请立即终止程序以避免不可预期的判定结果。 当你确定答案 $x$ 时，输出 `2 x`。

见交互方式。

### 评分标准 设 $n = \max(|a|, |b|, |c|)$，$m = \max(a_i, b_j, c_t)$。 1. （$6$ 分）：$n \leq 10$，$Q = 150$； 2. （$4$ 分）：$|b|=0$，$|c|=0$，$m \leq 2$，$Q = 150$； 3. （$9$ 分）：$|c|=0$，$m \leq 2$，$Q = 125$； 4. （$10$ 分）：$m \leq 2$，$Q = 125$； 5. （$13$ 分）：$|c|=0$，$Q = 1000$； 6. （$13$ 分）：$|c|=0$，$Q = 125$； 7. （$17$ 分）：$Q = 1000$； 8. （$21$ 分）：$Q = 125$； 9. （$7$ 分）：$Q = 65$。