logo AlgoBeat OnlineJudge
登录 注册

#214196. [POCamp 2022] 一安在?2 / Where's Waldo?

内存限制:1024 MiB 时间限制:11000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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


这是一道交互题。在本题中,交互库在每一轮中是非自适应的。请关注本题中排列的特殊性。

存在一个长度为 的隐藏排列 ,并保证其是均匀随机生成的。该排列以某种未知顺序恰好各包含一次数字

你可以选择位置 ,并提出如下形式的问题:「 的和是多少?」

你的任务是在尽可能少的提问次数内,找出 中数字 所在的位置。你的得分取决于你提问的次数。

实现细节

你的程序首先应在一行中读入两个整数 是程序将运行的轮数, 的长度。

接下来进行 轮:

当一轮开始时,你可以开始提问。输出一行 来询问位置 之间数值的和()。

每次提问之后,你的程序应读入一个整数,即该区间内数值的和。

当你找到了数字 所在的位置后,输出一行 ,其中 是满足 的下标。输出后开始下一轮(或终止程序)。

请确保在每次询问后刷新输出,否则可能会被判为 Time Limit Exceeded。在 C++ 中可以使用例如 cout << flushfflush(stdout);在 Python 中使用 stdout.flush();在 Java 中使用 System.out.flush()

输入格式

见「实现细节」。

输出格式

见「实现细节」。

样例

样例输入 1

2 10

55

40

1


1

样例输出 1


? 1 10

? 1 5

? 6 6

! 6
? 1 1

! 1

数据范围与提示

计分方式

你的程序将在唯一的一个测试点上进行测试,该测试点满足

如果任意一轮给出了错误答案,提交将被判为 Wrong Answer。

为你的程序在所有 中提出的问题总数。你的得分为 分。如果得到负分,则记为 分。

也就是说,如果你使用了超过 次询问,你将得到 分;如果使用了不超过 次询问,你将得到 分。介于两者之间时,得分按线性方式变化。