← 返回题目列表

Codeforces · 1746/E2

E2. 开玩笑(硬版)

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

本题与困难版的唯一区别是最大题数。

这是一个交互问题。

有一个隐藏的整数 $$$1 \le x \le n$$$ 你必须找到它。为了找到它,您最多可以提出 $$$\mathbf{53}$$$ 问题。

在每个问题中,您可以选择一个非空整数集合$$$S$$$,并询问$$$x$$$是否属于$$$S$$$,在每个问题之后,如果$$$x$$$属于$$$S$$$,您将收到“YES”,否则“NO”。

但问题是,并不是所有的答案都一定是真的(有些是开玩笑的),只是保证每两个连续的问题,至少有一个回答正确。

除了问题之外,您最多可以对答案 $$$x$$$ 进行 $$$2$$$ 猜测。每次你进行猜测时,如果你猜对了 $$$x$$$,你会收到“:)”并且你的程序应该终止,否则你会收到“:(”。

作为开玩笑的一部分,我们不会一开始就固定 $$$x$$$ 的值。相反,只要之前的所有响应都有效,如上所述,它就可以在整个交互过程中发生变化。

请注意,您的答案猜测总是正确的。如果您在猜测之前和之后提出问题,那么按照正常情况,这两个问题中至少有一个会被正确回答。

输入

输入的唯一行包含单个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),即 $$$x$$$ 的最大可能值。

互动

对于每一个问题,如果你想询问一个集合$$$S$$$,首先打印字符'?',然后打印$$$S$$$的大小,然后逐个打印$$$S$$$的元素。每个元素应该是 $$$1$$$ 和 $$$n$$$ 之间的整数,元素必须不同。在每个问题之后,阅读字符串“是”或“否”,如声明中所述。您最多可以提出 $$$53$$$ 这样的问题。

如果你想猜测 $$$x$$$,首先打印字符 '!'然后打印你的猜测。每次猜测后,读“:)”或“:(”。如果你猜对$$$x$$$,答案是“:)”,你的程序应该立即终止,否则你会收到“:(”。你最多可以做出$$$2$$$这样的猜测。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

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

此问题不允许进行黑客攻击。

示例

输入 #1

6
NO
:(
NO
:)

输出 #1

? 5 1 2 5 4 3
! 6
? 4 1 2 3 4
! 5

注意

如果第一个问题的答案是正确的,那么 $$$x$$$ 将等于 $$$6$$$,但正如我们在第一个猜测中看到的,$$$6$$$ 不是答案。

所以第一个问题的答案就是开玩笑。众所周知,我们两个问题中至少有一个的答案是正确的,既然第一个问题的答案是开玩笑,那么第二个问题的答案应该是正确的。

所以我们会明白 $$$x$$$ 不等于 $$$1, 2, 3$$$ 或 $$$4$$$,并且我们也知道 $$$x$$$ 也不等于 $$$6$$$。因此$$$x$$$应该等于$$$5$$$。