← 返回题目列表

Codeforces · 1275/F

F. 后分片

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

这是一项交互式任务。

当数据太多并且一台服务器无法容纳时,就必须对其进行分片。让我们考虑一个用于存储用户帖子的系统,该系统位于 $$$S$$$ 服务器上,从 1 开始编号。每次用户撰写帖子时,他都会获得一个范围从 1 到 $$$10^{18}$$$ 的唯一标识符,并保存到随机服务器上。帖子创建得越晚,其 $$$id$$$ 就越高。有时帖子会被删除,因此服务器上的帖子数量可能会明显不同。

让我们查看该用户所有未删除的 $$$id$$$ 帖子,并按升序对它们进行排序。您想知道其中的第 $$$k$$$ 个。为此,您可以发送不超过 100 个额外请求。每个请求的格式为“? $$$i$$$ $$$j$$$。”作为响应,您将收到第 $$$j$$$ 个用户帖子的标识符(在第 $$$i$$$ 服务器上存储的标识符中按升序排列)。当您认为您知道第 $$$k$$$ 个升序标识符时,您应该以“! $$$id$$$”格式打印响应,而不是查询。

互动

第一行包含两个数字 $$$n$$$ 和 $$$S$$$ ($$$1 \le n \le 100, 1 \le S \le 5$$$) — 需要独立解决问题的用户数量,以及存储帖子的服务器数量。

接下来你需要解决问题 $$$n$$$ 次。首先,您需要计算 $$$S$$$ 的数字 $$$a_1, a_2, ... a_S$$$ ($$$0 \le a_i; \sum a_i \le 10^5$$$) — 每个服务器上的用户帖子数量。下一行将指定数字 $$$k$$$ ($$$1 \le k \le \sum a_i $$$) - 您需要查找的按升序排列的帖子的标识符。

接下来,您需要按照条件中描述的格式发出不超过 100 个请求。

请注意,请求数量的限制分别适用于每个用户,因此,当进入下一个测试时,问题计数器将被重置。

示例

输入 #1

1 2
3 2
3

3

5

10

输出 #1

? 1 2

? 2 1

? 1 3

! 5

注意

在示例中,第一台服务器存储 $$$id$$$ 1、3 和 10 的帖子。第二台服务器存储 5 和 7。您需要找到第三个升序数字,即 5。