[UOI 2021] 第 k 小的数

ID: 14143

远端评测题

3000ms

256MiB

显示难度省选/NOI−

上传者:

标签>

2021

交互题

Special Judge

UOI（乌克兰）

题目描述

这是一道交互题。

哥萨克·武斯有三个秘密的正整数数组 $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。其中：

示例查询 1 3 10 表示获取数组 $c$ 的第 $10$ 个元素。

每次查询后，必须换行并刷新输出缓冲区，否则会得到 "超出时间限制" 的判定。刷新缓冲区的方法：

注意：如果查询无效（超出查询限制或不满足约束条件），交互器会输出 -1 并终止程序。如果读取到 -1，请立即终止程序以避免不可预期的判定结果。

当你确定答案 $x$ 时，输出 2 x。

见交互方式。

设 $n = \max(|a|, |b|, |c|)$ ， $m = \max(a_i, b_j, c_t)$ 。