← 返回题目列表

Codeforces · 1698/D

D. 定点猜测

中文机器翻译题面 查看原题

这是一个交互问题。

最初有一个数组 $$$a = [1, 2, \ldots, n]$$$,其中 $$$n$$$ 是奇数正整数。陪审团选择了 $$$\frac{n-1}{2}$$$ 不相交的元素对,然后交换这些对中的元素。例如,如果 $$$a=[1,2,3,4,5]$$$,并且交换 $$$1 \leftrightarrow 4$$$ 和 $$$3 \leftrightarrow 5$$$ 对,则生成的数组为 $$$[4, 2, 5, 1, 3]$$$。

由于这些交换,只有一个元素不会改变位置。你需要找到这个元素。

为此,您可以询问几个问题。在每个查询中,您可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$)。作为回报,您将获得按升序排序的子数组 $$$[a_l, a_{l + 1}, \dots, a_r]$$$ 的元素。

查找位置没有改变的元素。您最多可以进行 $$$\mathbf{15}$$$ 查询。

数组 $$$a$$$ 在交互之前是固定的,并且在查询后不会更改。

回想一下,数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$a$$$ 获得。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \leq n < 10^4$$$;$$$n$$$ 为奇数)——数组 $$$a$$$ 的长度。

阅读每个测试用例的第一行后,您应该开始交互。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^4$$$。

互动

对于每个测试用例,通过读取整数 $$$n$$$ 开始交互。

要进行查询,请输出不带引号的 "$$$\texttt{?}\;l\;r$$$" ($$$1 \leq l \leq r \leq n$$$)。然后,您应该读入 $$$r-l+1$$$ 整数 - 整数 $$$a_l, a_{l + 1}, \dots, a_r$$$,按升序排列。您最多可以在单个测试用例中进行 $$$15$$$ 此类查询。

如果您收到整数 $$$-1$$$ 而不是答案或整数 $$$n$$$,则意味着您的程序进行了无效查询,超出了查询限制,或者对先前的测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

当您准备好给出最终答案时,输出不带引号的 "$$$\texttt{!}\;x$$$" ($$$1 \leq x \leq n$$$) — 未更改位置的元素。给出此答案不计入 $$$15$$$ 查询的限制。之后,您的程序必须继续解决剩余的测试用例,或者如果所有测试用例都已解决则退出。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

要进行破解,请使用以下格式。第一行必须包含一个整数 $$$t$$$ ($$$1 \leq t \leq 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行必须包含一个整数 $$$n$$$($$$3 \leq n < 10^4$$$;$$$n$$$ 为奇数)——数组 $$$a$$$ 的长度。

每个测试用例的第二行必须包含 $$$n$$$ 以空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — $$$a$$$ 的元素。数组 $$$a$$$ 应该是数组 $$$[1,2,\dots,n]$$$ 上 $$$\frac{n-1}{2}$$$ 不相交交换的结果。

示例

输入 #1

2
5

1 2 4 5

1 3 5

3

1

输出 #1

? 1 4

? 3 5

! 2

? 1 1

! 1

注意

在第一个测试中,交互进行如下。

SolutionJuryExplanation$$$\texttt{2}$$$有2个测试用例。$$$\texttt{5}$$$在第一个测试用例中,隐藏数组是$$$[4,2,5,1,3]$$$,长度为$$$5$$$。$$$\texttt{? 1 4}$$$$$$\texttt{1 2 4 5}$$$解决方案按升序请求子数组$$$[4,2,5,1]$$$,陪审团以$$$[1,2,4,5]$$$.$$$\texttt{? 3 5}$$$$$$\texttt{1 3 5}$$$该解决方案以升序请求子数组 $$$[5,1,3]$$$,陪审团以 $$$[1,3,5]$$$.$$$\texttt{! 2}$$$解决方案以某种方式确定$$$a_2=2$$$,并将其输出。由于输出正确,陪审团继续进行下一个测试用例。$$$\texttt{3}$$$在第二个测试用例中,隐藏数组为$$$[1,3,2]$$$,长度为$$$3$$$。$$$\texttt{? 1 1}$$$$$$\texttt{1}$$$该解决方案仅请求数字 $$$[1]$$$,陪审团以 $$$[1]$$$.$$$\texttt{! 1}$$$解确定$$$a_1=1$$$,并将其输出。由于输出是正确的并且没有更多的测试用例,陪审团和解决方案退出。

请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。