AT_nupc2024_k.A Shortcut

本题是一个交互式问题（你的程序将与评测程序通过输入输出进行交互）。

给定一个整数 $N$，评测机会隐藏一个由 $N$ 个顶点组成的无向图 $G$，其结构如下：

• $G$ 的每个顶点编号为 $1$ 到 $N$。
• 对于所有满足 $1 \le i < N$ 的整数 $i$，顶点 $i$ 和顶点 $i+1$ 之间有一条边。
• 存在唯一一组满足 $y - x > 1$ 且 $1 \le x, y \le N$ 的整数对 $(x, y)$，使得顶点 $x$ 和顶点 $y$ 之间存在一条边。
• 除上述 $N$ 条边外，不存在其他边。

你可以对 $G$ 进行如下操作来查询信息：

• 任选两个顶点编号 $p, q$，询问从顶点 $p$ 到顶点 $q$ 的最短路径（即经过的边的条数）。

请你在不超过 $\lceil \log_2 N + 1 \rceil$ 次查询之内，确定出 $(x, y)$。

评测机会提供 $T$ 组测试数据，请你对每一组测试数据都找出 $(x, y)$。

首先，标准输入会给出一个整数 $T$。

$T$

接着，有 $T$ 组测试数据。每组测试数据格式如下：

首先，输入一个整数 $N$。

$N$

然后，在每组数据中，你最多可以进行 $\lceil \log_2 N + 1 \rceil$ 次查询。
每次查询请输出如下格式到标准输出，其中 $p, q$ 满足 $1 \leq p, q \leq N$：

? $p$ $q$

每个查询后，会从标准输入获得一个响应，格式如下：

$\mathrm{dist}(p, q)$

其中 $\mathrm{dist}(p, q)$ 表示从顶点 $p$ 到顶点 $q$ 的最短路径长度。如果你的查询不合法，或查询次数超过 $\lceil \log_2 N + 1 \rceil$ 次，评测机会输出 $-1$。

评测机输出 $-1$ 时，无论剩余测试数据如何，你的解答均被判为不正确，请立即退出程序。

确定 $(x, y)$ 后，请按如下格式输出，这不计入查询次数：

! $x$ $y$

随后若有下一组测试数据，请继续解答。所有测试数据回答完毕后，请终止程序。

无

注意事项

• 每次输出后请务必输出换行并刷新标准输出，否则可能会因为 TLE 被判失败。
• 评测机对非法输出和非法操作的判定可能不确定，请谨慎处理输入输出。
• $(x, y)$ 在你进行交互之前已经被固定，交互过程中不会变化。

输入输出样例

输入	输出	说明
2		首先输入一个整数 $T$。
10		第一组测试数据，首先输入一个整数 $N$。
? 1 10		查询 $p = 1, q = 10$。
6		得到 $\mathrm{dist}(1, 10)=6$。
? 8 6		查询 $p = 8, q = 6$。
2		得到 $\mathrm{dist}(8, 6)=2$。
? 3 7		查询 $p = 3, q = 7$。
1		得到 $\mathrm{dist}(3, 7)=1$。
! 3 7		输出 $(x, y) = (3, 7)$ 作为答案。可以通过。
3		第二组测试数据，首先输入一个整数 $N$。
? 1 2		查询 $p = 1, q = 2$。
1		得到 $\mathrm{dist}(1, 2)=1$。
! 1 3		输出 $(x, y) = (1, 3)$ 作为答案。可以通过。所有测试用例解答完毕，程序应终止。

数据范围

• $1 \leq T \leq 10^3$
• $3 \leq N \leq 10^9$
• $1 \le x < y \le N$
• $y - x > 1$
• $T, N, x, y$ 均为整数

由 ChatGPT 5 翻译