题目描述
这是一道交互题。交互库是非自适应的。
有一个隐藏的 1∼N 的排列 p1,…,pN。
你可以提问交互库至多 K 次,每次给定 i,j(1≤i<j≤N),交互库会回答 pi,pi+1,…,pj 中次大元素的下标。
在你提问完后,交互库会向你提问 Q 次,每次给定 a,b(1≤a<b≤N),你需要回答 pa,pa+1,…,pb 中次大元素的下标。
请注意:在你提问完之后,才能得知交互库的提问。这 Q 次交互库对你的提问一次性给出。
实现细节
首先读入正整数 N。
接下来,发起至多 K 次提问:
- ? i j:提问 pi,pi+1,…,pj 中次大元素的下标。
- 你需要保证 1≤i<j≤N。
- !:结束提问。
每次提问后,都需要换行并刷新缓冲区。
在结束提问后,读入正整数 Q,以及 Q 对正整数 a,b,表示对交互库你的提问。交互库保证 1≤a<b≤N。
对于每个交互库的提问,输出一行一个正整数,表示次大元素的下标。
在你回答完所有询问后,你需要刷新缓冲区,然后终止程序运行。
交互库是非自适应的。也就是说,询问和排列在交互开始前就已经固定。
输入格式
见「实现细节」。
输出格式
见「实现细节」。
4
2
1
2
1 4
2 3
? 1 2
? 1 3
!
4
2
提示
样例解释
样例的排列为 p=[2,1,4,3]。
数据范围
- N≤512;
- K=Q=2048。
子任务
子任务 0 为样例。
其中,「−」表示「不保证」。
子任务编号 |
N≤ |
特殊性质 |
得分 |
1 |
64 |
− |
6 |
2 |
− |
A |
10 |
3 |
B |
11 |
4 |
C |
13 |
5 |
256 |
− |
26 |
6 |
− |
34 |
- 特殊性质 A:不存在 i 使得 pi>max{pi−1,pi+1}。
- 特殊性质 B:p1=N。
- 特殊性质 C:不存在 i 使得 pi<min{pi−1,pi+1}。
交互库是非自适应的。也就是说,询问和排列在交互开始前就已经固定。