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

    ID: 14143 远端评测题 3000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2021交互题Special JudgeUOI(乌克兰)

[UOI 2021] 第 k 小的数

题目描述

这是一道交互题。

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

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

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

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

输入格式

第一行包含五个整数 a|a|b|b|c|c|kkgg0a,b,c1060 \leq |a|, |b|, |c| \leq 10^61ka+b+c1 \leq k \leq |a| + |b| + |c|)。

保证所有数组中的元素都在 [1,109][1, 10^9] 范围内。

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

交互方式

首先读取五个整数 a|a|b|b|c|c|kkgg

要发起查询,输出 1 r m。其中:

  • rr 表示数组编号(11 对应数组 aa22 对应数组 bb33 对应数组 cc);
  • mm 表示该数组中的位置(例如,m=1m=1 表示第一个元素,m=am=|a| 表示最后一个元素)。

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

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

  • C++: fflush(stdout)cout.flush()
  • Java: System.out.flush()
  • Pascal: flush(output)
  • Python: stdout.flush(); 其他语言请参考相关文档。

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

当你确定答案 xx 时,输出 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

提示

评分标准

n=max(a,b,c)n = \max(|a|, |b|, |c|)m=max(ai,bj,ct)m = \max(a_i, b_j, c_t)

  1. 66 分):n10n \leq 10Q=150Q = 150
  2. 44 分):b=0|b|=0c=0|c|=0m2m \leq 2Q=150Q = 150
  3. 99 分):c=0|c|=0m2m \leq 2Q=125Q = 125
  4. 1010 分):m2m \leq 2Q=125Q = 125
  5. 1313 分):c=0|c|=0Q=1000Q = 1000
  6. 1313 分):c=0|c|=0Q=125Q = 125
  7. 1717 分):Q=1000Q = 1000
  8. 2121 分):Q=125Q = 125
  9. 77 分):Q=65Q = 65