#P12575. [UOI 2021] 第 k 小的数
[UOI 2021] 第 k 小的数
题目描述
这是一道交互题。
哥萨克·武斯有三个秘密的正整数数组 、 和 。它们的长度分别为 、 和 ,这些长度不一定相同。已知每个数组都是已排序的,即每个后续元素都不小于前一个元素。
你想获取关于这些数组的特定信息——即在三个数组合并后的排序数组中第 小的元素值。也就是说,如果将这三个数组合并成一个长度为 的大数组并从小到大排序,你需要找出排序后数组中的第 个元素。
哥萨克·武斯拒绝直接展示这些数组给你。但他同意以下交互方式:你可以查询特定数组中的特定位置的元素值。你可以选择一个数组和一个位置,哥萨克会告诉你该位置上的元素值。注意,你可以多次进行这种查询操作,且不限于同一个数组。由于哥萨克非常忙碌,他最多允许你提出 次查询。
你的任务是找出三个数组合并后第 小的元素。
输入格式
第一行包含五个整数 、、、 和 (,)。
保证所有数组中的元素都在 范围内。
整数 ()表示测试用例的分组编号(参见评分标准)。
交互方式
首先读取五个整数 、、、 和 。
要发起查询,输出 1 r m
。其中:
- 表示数组编号( 对应数组 , 对应数组 , 对应数组 );
- 表示该数组中的位置(例如, 表示第一个元素, 表示最后一个元素)。
示例查询 1 3 10
表示获取数组 的第 个元素。
每次查询后,必须换行并刷新输出缓冲区,否则会得到 "超出时间限制" 的判定。刷新缓冲区的方法:
- C++:
fflush(stdout)
或cout.flush()
; - Java:
System.out.flush()
; - Pascal:
flush(output)
; - Python:
stdout.flush()
; 其他语言请参考相关文档。
注意:如果查询无效(超出查询限制或不满足约束条件),交互器会输出 -1
并终止程序。如果读取到 -1
,请立即终止程序以避免不可预期的判定结果。
当你确定答案 时,输出 2 x
。
输出格式
见交互方式。
3 3 3 2 0
2
5
5
2
6
6
6
7
10
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 2
提示
评分标准
设 ,。
- ( 分):,;
- ( 分):,,,;
- ( 分):,,;
- ( 分):,;
- ( 分):,;
- ( 分):,;
- ( 分):;
- ( 分):;
- ( 分):。