P14099 [POCamp 2022] 一安在？2 / Where's Waldo?

为了方便调试，我们在附件中提供了交互库。

**这是一道交互题。在本题中，交互库在每一轮中是非自适应的。请关注本题中排列的特殊性。** 存在一个长度为 $ N $ 的隐藏排列 $ P_1, P_2, \dots, P_N $，并**保证其是均匀随机生成的**。该排列以某种未知顺序恰好各包含一次数字 $ 1, 2, 3, \dots, N $。 你可以选择位置 $ l $ 和 $ r $，并提出如下形式的问题：「$ P_l + P_{l+1} + \dots + P_r $ 的和是多少？」 你的任务是在尽可能少的提问次数内，找出 $ P $ 中数字 $ 1 $ 所在的位置。你的得分取决于你提问的次数。 ### 实现细节 你的程序首先应在一行中读入两个整数 $ T $ 和 $ N $。$ T $ 是程序将运行的轮数，$ N $ 是 $ P $ 的长度。 接下来进行 $ T $ 轮： 当一轮开始时，你可以开始提问。输出一行 $\texttt{? a b}$ 来询问位置 $ a $ 到 $ b $ 之间数值的和（$ 1 \le a \le b \le N $）。 每次提问之后，你的程序应读入一个整数，即该区间内数值的和。 当你找到了数字 $ 1 $ 所在的位置后，输出一行 $\texttt{! i}$，其中 $ i $ 是满足 $ P_i = 1 $ 的下标。输出后开始下一轮（或终止程序）。 请确保在每次询问后刷新输出，否则可能会被判为 Time Limit Exceeded。在 C++ 中可以使用例如 `cout

见「实现细节」。

见「实现细节」。

### 计分方式 你的程序将在唯一的一个测试点上进行测试，该测试点满足 $ N = T = 1000 $。 如果任意一轮给出了错误答案，提交将被判为 Wrong Answer。 令 $ M $ 为你的程序在**所有 $\boldsymbol{T}$ 轮**中提出的问题总数。你的得分为 $ \min(100, 220 - \frac{M}{2500}) $ 分。如果得到负分，则记为 $ 0 $ 分。 也就是说，如果你使用了超过 $ 550,000 $ 次询问，你将得到 $ 0 $ 分；如果使用了不超过 $ 300,000 $ 次询问，你将得到 $ 100 $ 分。介于两者之间时，得分按线性方式变化。