← 返回题目列表

Codeforces · 1520/F1

F1. 猜第 K 个零(简单版)

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

这是一个交互问题。

这是问题的简单版本。与困难版本的区别在于,简单版本中 $$$t=1$$$ 并且查询次数限制为 $$$20$$$。

Polycarp 正在玩电脑游戏。在这个游戏中,隐藏了一个由 0 和 1 组成的数组。如果波利卡普猜出左边第 $$$k$$$ 次零的位置 $$$t$$$ 次,他就获胜。

Polycarp 最多可以提出 $$$20$$$ 以下类型的请求:

- ? $$$l$$$ $$$r$$$ — 找出从 $$$l$$$ 到 $$$r$$$ ($$$1 \le l \le r \le n$$$) 位置的所有元素的总和。

在这个(简单版本)问题中,这一段并没有真正意义,因为 $$$t=1$$$ 总是。为了让游戏变得更有趣,每个猜测的零都会变成一,并且游戏在改变的数组上继续。更正式地说,如果第 $$$k$$$ 个零的位置是 $$$x$$$,那么在 Polycarp 猜测这个位置后,数组的第 $$$x$$$ 个元素将从 $$$0$$$ 替换为 $$$1$$$。当然,此功能仅影响 $$$t>1$$$ 的情况。

帮助波利卡普赢得比赛。

互动

首先,您的程序必须读取两个整数 $$$n$$$ 和 $$$t$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$t=1$$$)。

接下来是 $$$t$$$ 行,每一行包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$)。保证在请求时数组至少包含 $$$k$$$ 个零。为了获得 $$$k$$$ 的下一个值,您必须输出 $$$k$$$ 当前值的答案。

此后,您最多可以提出 $$$20$$$ 请求。

使用以下格式输出答案(这不是请求,不计入$$$20$$$):

- ! $$$x$$$ — 第 $$$k$$$ 个零的位置。

数组中的位置从左到右编号,从 $$$1$$$ 到 $$$n$$$(含)。

打印 $$$t$$$ 答案后,你的程序应该立即退出。

在此任务中,交互器不具有自适应性。这意味着在同一测试中,隐藏数组和查询不会改变。

如果查询错误,将显示-1。当收到此值时,您的程序必须立即正常退出(例如,通过调用 exit(0)),否则,测试系统可能会发出任意判决。

如果超过请求次数,将显示判定错误答案。

如果您不打印任何内容或忘记刷新输出缓冲区,您的解决方案可能会得到超出空闲限制的判决。

要刷新输出缓冲区,您需要在查询输出和行尾字符之后立即执行以下操作:

- C ++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

黑客

使用以下格式进行黑客攻击:

在第一行打印字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$),由零和一组成,以及一个整数 $$$t$$$ ($$$t = 1$$$) - 分别是隐藏数组和请求数。在接下来的 $$$t$$$ 行中输出数字 $$$k$$$ ($$$1 \le k \le |s|$$$)。

被黑客攻击的解决方案将无法直接访问隐藏数组。

示例

输入 #1

6 1
2

2

1

1

0

0

输出 #1

? 4 6

? 1 1

? 1 2

? 2 2

? 5 5

! 5

注意

在第一个测试中,$$$[1, 0, 1, 1, 0, 1]$$$ 数组被隐藏。在此测试中 $$$k=2$$$。