CF1746E2 Joking (Hard Version)

本题与难度更低的版本唯一的区别在于最多可提问的问题数。 这是一个交互题。 有一个隐藏的整数 $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$ 之间的整数，且元素互不相同。每次提问后，读取一个字符串 "YES" 或 "NO"，如题目描述。你最多可以进行 $53$ 次这样的提问。 如果你想猜测 $x$ 的值，先输出字符 '!'，然后输出你的猜测。每次猜测后，读取 ":)" 或 ":("。如果你猜中了 $x$，答案为 ":)"，你的程序应立即终止，否则收到 ":("。你最多可以进行 $2$ 次这样的猜测。 每次输出后不要忘记换行并刷新输出缓冲区，否则会收到 Idleness limit exceeded 错误。具体操作如下： - C++ 使用 fflush(stdout) 或 cout.flush()； - Java 使用 System.out.flush()； - Pascal 使用 flush(output)； - Python 使用 stdout.flush()； - 其它语言请查阅相关文档。 本题不允许 Hack。

如果第一次提问的答案是真的，那么 $x$ 就等于 $6$，但从第一次猜测可以看出 $6$ 并不是答案。 所以第一次提问的答案是开玩笑的。由于保证两次提问中至少有一次回答是正确的，既然第一次是假的，第二次就一定是真的。 因此我们可以确定 $x$ 不等于 $1, 2, 3, 4$，并且也不等于 $6$。所以 $x$ 应该等于 $5$。 由 ChatGPT 4.1 翻译