CF1729E Guess the Cycle Size

这是一个交互题。 我想和你玩一个游戏…… 我们为你隐藏了一个有 $n$ 个顶点的环形图（$3 \le n \le 10^{18}$）。环形图是一个无向图，$n$ 个顶点构成一个环。每个顶点都属于这个环，也就是说环的长度（即其中的边数）恰好为 $n$。环中顶点的顺序是任意的。 你可以通过以下方式进行询问： - "? a b"，其中 $1 \le a, b \le 10^{18}$ 且 $a \neq b$。对于每次询问，交互器会在单独一行输出从顶点 $a$ 到顶点 $b$ 的两条路径中的一条的长度（随机选取），或者如果 $\max(a, b) > n$，则输出 $-1$。路径的长度指的是路径上的边数。 如果你能在不超过 $50$ 次询问内猜出隐藏图的顶点数（即 $n$），你就获胜了。 注意，交互器的实现保证，对于任意有序对 $(a, b)$，无论你询问多少次 "? a b"，它总是返回相同的值。注意，"? b a" 的答案可能不同。 图中的顶点编号是随机排列的，并且在游戏开始前已经固定。 本题禁止 Hack。评测机的测试点数量为 $50$。

无

你最多可以进行 $50$ 次询问。每次询问，输出一行： - "? a b"，其中 $1 \le a, b \le 10^{18}$ 且 $a \neq b$。交互器会在单独一行输出从顶点 $a$ 到顶点 $b$ 的一条简单路径的长度（不是从 $b$ 到 $a$ 的路径），或者如果 $\max(a, b) > n$，则输出 $-1$。交互器以等概率选择两条路径中的一条。 如果你的某次询问返回了 $0$，说明你的解已经被判为“答案错误”（例如你询问次数超过 $50$ 次或询问不合法）。此时你的程序应立即终止。否则，在这种情况下你可能会收到“运行错误”、“超时”或其他非“答案错误”的判定。 输出答案时，与询问一样，单独输出一行。输出答案不计入 $50$ 次询问次数。格式如下： - "! n"：你认为隐藏图的顶点数（$3 \le n \le 10^{18}$）。 输出后你的程序应立即终止。 每次输出后请务必刷新输出流，防止输出被缓冲。例如，C++ 使用 flush(stdout)，Java 调用 System.out.flush()，Pascal 用 flush(output)，Python 用 stdout.flush()。 注意，交互器的实现保证，对于任意有序对 $(a, b)$，无论你询问多少次 "? a b"，它总是返回相同的值。注意，"? b a" 的答案可能不同。 图中的顶点编号是随机排列的，并且在游戏开始前已经固定。 本题禁止 Hack。评测机的测试点数量为 $50$。

在第一个样例中，图可能如下所示：  在这种情况下，所有顶点对之间的简单路径长度都是 $1$ 或 $2$。 - 第一次询问发现，从顶点 $1$ 到顶点 $2$ 的一条简单路径长度为 $1$。 - 第二次询问发现，从顶点 $1$ 到顶点 $3$ 的一条简单路径长度为 $2$。 - 第三次询问发现，顶点 $4$ 不在图中。因此，图的大小为 $3$。 由 ChatGPT 4.1 翻译