#P12446. [COTS 2025] 答好位 / Vrsta

    ID: 14019 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>2025交互题Special JudgeCOI(克罗地亚)

[COTS 2025] 答好位 / Vrsta

题目描述

这是一道交互题。交互库是非自适应的。

有一个隐藏的 1N1\sim N 的排列 p1,,pNp_1,\ldots,p_N

你可以提问交互库至多 KK 次,每次给定 i,ji,j1i<jN1\le i\lt j\le N),交互库会回答 pi,pi+1,,pjp_{i},p_{i+1},\ldots,p_{j} 中次大元素的下标。

在你提问完后,交互库会向你提问 QQ 次,每次给定 a,ba,b1a<bN1\le a\lt b\le N),你需要回答 pa,pa+1,,pbp_{a},p_{a+1},\ldots,p_{b} 中次大元素的下标。

请注意:在你提问完之后,才能得知交互库的提问。这 QQ 次交互库对你的提问一次性给出。

实现细节

首先读入正整数 NN

接下来,发起至多 KK 次提问:

  • ?\texttt{?} ii jj:提问 pi,pi+1,,pjp_{i},p_{i+1},\ldots,p_{j} 中次大元素的下标。
    • 你需要保证 1i<jN1\le i\lt j\le N
  • !\texttt{!}:结束提问。

每次提问后,都需要换行并刷新缓冲区。

在结束提问后,读入正整数 QQ,以及 QQ 对正整数 a,ba,b,表示对交互库你的提问。交互库保证 1a<bN1\le a\lt b\le N

对于每个交互库的提问,输出一行一个正整数,表示次大元素的下标。

在你回答完所有询问后,你需要刷新缓冲区,然后终止程序运行。

交互库是非自适应的。也就是说,询问和排列在交互开始前就已经固定。

输入格式

见「实现细节」。

输出格式

见「实现细节」。

4

2

1

2
1 4
2 3



? 1 2

? 1 3

!



4
2

提示

样例解释

样例的排列为 p=[2,1,4,3]p=[2,1,4,3]

数据范围

  • N512N\le 512
  • K=Q=2048K=Q=2\, 048

子任务

子任务 00 为样例。

其中,「-」表示「不保证」。

子任务编号 NN\le 特殊性质 得分
11 6464 - 66
22 - A\text{A} 1010
33 B\text{B} 1111
44 C\text{C} 1313
55 256256 - 2626
66 - 3434
  • 特殊性质 A\text{A}:不存在 ii 使得 pi>max{pi1,pi+1}p_i\gt \max\{p_{i-1},p_{i+1}\}
  • 特殊性质 B\text{B}p1=Np_1=N
  • 特殊性质 C\text{C}:不存在 ii 使得 pi<min{pi1,pi+1}p_i\lt \min\{p_{i-1},p_{i+1}\}

交互库是非自适应的。也就是说,询问和排列在交互开始前就已经固定。