logo AlgoBeat OnlineJudge
登录 注册

#212638. [UOI 2021] 第 k 小的数

内存限制:256 MiB 时间限制:3000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

这是一道交互题。

哥萨克·武斯有三个秘密的正整数数组 。它们的长度分别为 ,这些长度不一定相同。已知每个数组都是已排序的,即每个后续元素都不小于前一个元素。

你想获取关于这些数组的特定信息——即在三个数组合并后的排序数组中第 小的元素值。也就是说,如果将这三个数组合并成一个长度为 的大数组并从小到大排序,你需要找出排序后数组中的第 个元素。

哥萨克·武斯拒绝直接展示这些数组给你。但他同意以下交互方式:你可以查询特定数组中的特定位置的元素值。你可以选择一个数组和一个位置,哥萨克会告诉你该位置上的元素值。注意,你可以多次进行这种查询操作,且不限于同一个数组。由于哥萨克非常忙碌,他最多允许你提出 次查询。

你的任务是找出三个数组合并后第 小的元素。

输入格式

第一行包含五个整数 )。

保证所有数组中的元素都在 范围内。

整数 )表示测试用例的分组编号(参见评分标准)。

交互方式

首先读取五个整数

要发起查询,输出 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

输出格式

见交互方式。

样例

样例输入 1

3 3 3 2 0

2

5

5

2

6

6

6

7

10

样例输出 1


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

数据范围与提示

评分标准

  1. 分):
  2. 分):
  3. 分):
  4. 分):
  5. 分):
  6. 分):
  7. 分):
  8. 分):
  9. 分):