#H1026. 「MCOI-07」Dream and More Discs

「MCOI-07」Dream and More Discs

题目背景

本题为 IO 交互题。

题目描述

Dream 将 Tommy 的所有音乐盘分为 nn 类,其中第 ii 类有 2m12^m-1 片音乐盘。所有盘都有一个唯一的正整数重要度。
现在 Dream 已经把所有类之内的音乐盘按照重要度递增排序。Dream 想知道所有盘中重要度第 kk 小是哪个盘。

由于音乐盘数量实在太多,Dream 不能直接给你所有音乐盘的重要度。在寻找答案时,Dream 允许你访问第 ii 类重要度第 jj 小的盘重要度值。

输入格式

交互开始时,评测机输入第一行为四个正整数 nnmmkk,和 ThTh,其中 ThTh 为最多应用访问次数。
每一次访问,评测机会回复所访问位置的音乐盘重要度。

输出格式

你的程序可以进行两个操作:

  1. ? i j,表示访问第 ii 类型第 jj 小音乐盘重要度。评测机会回复这位置重要度。
  2. ! i j,表示报告全局第 kk 小音乐盘为第 ii 类的第 jj 小音乐盘。
2 2 2 22

222

? 2 2

! 2 2

说明/提示

样例 1 解释

Dream 的音乐盘重要度为 [[2222,22222,222222],[22,222,2222222]][[2222,22222,222222],[22,222,2222222]]
第 2 类型为 [22,222][22,222];第 2 类型的第 2 小重要度为 222222
全局第 2 小重要度也是这音乐盘。

数据规模与约定

本题采用捆绑测试。

Subtask 分值 nn mm kk ThTh
1 1 pts 11 15,00015,000
2 9 pts 5050 88
3 19 pts 2020 1111
4 17 pts 5050 6,6666,666
5 23 pts 2,3332,333
6 31 pts 1,1111,111

对于所有数据,1kn(2m1)1\le k\le n(2^m-1),所有音乐盘的重要度互不相同并且小于等于 101810^{18}