这是一个交互问题。
这是问题的简单版本。与困难版本的区别在于,简单版本中 $$$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$$$。