Joking (Hard Version)

题意翻译

**本题和[简单版](https://www.luogu.com.cn/problem/CF1746E1)的区别在于询问次数的限制，在本题中你可以询问至多 $\mathbf{53}$ 次**。 **本题是 IO 交互题。** ### 题目描述 给定整数 $n$。 交互器有一个隐藏的整数 $x$，满足 $1\leq x\leq n$，你需要通过至多 $\mathbf{53}$ 次下列询问求出这个 $x$： - 给定非空整数集合 $S$，满足 $S$ 中的元素都是 $[1,n]$ 中的整数。 交互器会告诉你 $x\in S$ 是否成立。成立会回复 `YES`，否则会回复 `NO`。 但是，交互器可以选择说谎话，我们只保证交互器对任意两次连续询问的回复中至少有一次回复是真的。 除此之外，你还可以对 $x$ 进行至多 $\mathbf{2}$ 次直接猜测： - 给定整数 $y$，满足 $1\leq y\leq n$。 交互器会告诉你 $x=y$ 是否成立。成立会回复 `:)`，否则会回复 `:(`。 当你得到 `:)` 作为回复时你的程序就会被视为通过。 交互器**不会**在对 $x$ 的直接猜测上说谎。 如果你在某次猜测的前后各进行了一次询问，这两次询问的回复也至少有一个是真的。 **交互器是适应性的**，即 $x$ 的值可能会在交互过程中改变。保证交互器的 $x$ 总是满足上述询问限制。 ### 交互格式 首先，读入一个整数 $n(1\leq n\leq10^5)$ 表示 $x$ 的范围。接下来： - 如果你希望进行询问： 按照 `? k S[1] S[2] ... S[k]` 的格式输出你想询问的集合 $S$ 的大小 $k$ 和集合 $S$ 中的所有元素 $S_1,S_2,\cdots,S_k$。 然后读入一个字符串（只会是 `YES` 和 `NO` 中的一个）表示交互器的回复。 你需要保证 $1\leq k,S_i\leq n$ 且 $S$ 中的元素互不相同。 你只能进行至多 $\mathbf{53}$ 次上述询问。 - 如果你希望进行猜测： 按照 `! y` 的格式输出你想猜测的整数 $y$。 然后读入一个字符串（只会是 `:)` 和 `:(` 中的一个）表示交互器的回复。 你需要保证 $1\leq y\leq n$。 你只能进行至多 $\mathbf{2}$ 次上述询问。 一旦你得到了 `:)` 作为回答，你需要立刻结束程序。 注意刷新缓冲区。 ### 样例解释 下面展示了样例的交互过程： - 给定 $n=6$。 - 首先样例程序询问集合 $\{1,2,5,4,3\}$，交互器给出 `NO` 的回复。 可以推断出，如果交互器在第一次的询问中说了真话，答案就是 $6$。 - 接下来样例程序猜测 $x=6$，交互器给出 `:(` 的回复。 发现答案并不是 $6$，说明交互器在第一次询问中说了谎。 利用“交互器两次连续询问的回复必定有至少一个是真的”这个性质，我们可以推断出下一次询问交互器不能说谎。 - 接下来样例程序询问集合 $\{1,2,3,4\}$，交互器给出 `NO` 的回复。 由于交互器这次没有说谎，$1\sim6$ 的整数中就只剩下 $5$ 可能是 $x$。 - 最终样例程序猜测 $x=5$，交互器给出 `:)` 的回复。

题目描述

The only difference between this problem and the hard version is the maximum number of questions. This is an interactive problem. There is a hidden integer $ 1 \le x \le n $ which you have to find. In order to find it you can ask at most $ \mathbf{53} $ questions. In each question you can choose a non-empty integer set $ S $ and ask if $ x $ belongs to $ S $ or not, after each question, if $ x $ belongs to $ S $ , you'll receive "YES", otherwise "NO". But the problem is that not all answers are necessarily true (some of them are joking), it's just guaranteed that for each two consecutive questions, at least one of them is answered correctly. Additionally to the questions, you can make at most $ 2 $ guesses for the answer $ x $ . Each time you make a guess, if you guess $ x $ correctly, you receive ":)" and your program should terminate, otherwise you'll receive ":(". As a part of the joking, we will not fix the value of $ x $ in the beginning. Instead, it can change throughout the interaction as long as all the previous responses are valid as described above. Note that your answer guesses are always answered correctly. If you ask a question before and after a guess, at least one of these two questions is answered correctly, as normal.

输入输出格式

输入格式

The only line of the input contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ), the maximum possible value of $ x $ .

输出格式

For each question, if you want to ask about a set $ S $ , first print the character '?', then print the size of $ S $ and then print the elements of $ S $ one by one. Each element should be an integer between $ 1 $ and $ n $ , the elements must be distinct. After each question, read a string "YES" or "NO", as explained in the statement. You can make at most $ 53 $ such questions. If you want to guess for $ x $ , first print the character '!' and then print your guess. After each guess, read ":)" or ":(". If you guess $ x $ correctly, the answer is ":)" and your program should terminate immediately, otherwise you'll receive ":(". You can make at most $ 2 $ such guesses. After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. Hacking is not allowed in this problem.

输入输出样例

输入样例 #1

6

NO

:(

NO

:)

输出样例 #1

? 5 1 2 5 4 3

! 6

? 4 1 2 3 4

! 5

说明

If the answer of the first question were correct, then $ x $ would have been equal to $ 6 $ , but as we can see in the first guess, $ 6 $ is not the answer. So the answer of the first question is joking. As we know, the answer of at least one of our two questions is correct, since the answer of the first question was joking, the answer of the second question should be correct. So we will understand that $ x $ is not equal to $ 1, 2, 3 $ or $ 4 $ , and we also knew that $ x $ is not equal to $ 6 $ either. Hence $ x $ should be equal to $ 5 $ .

**题目大意：**

这个问题是一个交互式问题。有一个隐藏的整数 $ x $ 满足 $ 1 \le x \le n $，你需要通过最多 53 次询问来找出这个 $ x $。每次询问你可以选择一个非空的整数集合 $ S $，然后询问 $ x $ 是否属于集合 $ S $。如果 $ x $ 属于 $ S $，你会得到回复 "YES"，否则得到 "NO"。但是，回答有可能是不真实的，我们只能保证在任意连续两次询问中至少有一次是真的。

除此之外，你还可以对 $ x $ 进行最多 2 次直接猜测。每次猜测后，如果猜对了，你会得到回复 ":)"，否则得到 ":("。一旦你得到了 ":)" 作为回答，你的程序就应该立即结束。

交互器在对 $ x $ 的直接猜测上不会说谎。如果你在某次猜测的前后各进行了一次询问，这两次询问的回复也至少有一个是真的。交互器是适应性的，即 $ x $ 的值可能会在交互过程中改变，但保证交互器的 $ x $ 总是满足上述询问限制。

**输入输出数据格式：**

- **输入格式：** 输入的第一行包含一个整数 $ n $ ($ 1 \le n \le 10^5 $)，表示 $ x $ 的最大可能值。
- **输出格式：** 对于每次询问，如果你想询问一个集合 $ S $，首先输出字符 '?'，然后输出集合 $ S $ 的大小和集合 $ S $ 中的所有元素。每个元素应该是介于 $ 1 $ 和 $ n $ 之间的整数，且 $ S $ 中的元素必须互不相同。每次询问后，读取一个字符串 "YES" 或 "NO"，如题目所述。你可以进行最多 53 次这样的询问。

如果你想猜测 $ x $，首先输出字符 '!'，然后输出你的猜测。每次猜测后，读取 ":)" 或 ":("。如果你猜对了 $ x $，答案就是 ":)"，你的程序应该立即结束，否则你会得到 ":("。你可以进行最多 2 次这样的猜测。

在输出查询后不要忘记输出换行符并刷新输出缓冲区，否则你将得到超时错误。具体刷新方法根据使用的编程语言而异。

**样例解释：**

给定 $ n=6 $。

- 样例程序首先询问集合 $ \{1,2,5,4,3\} $，交互器给出 "NO" 的回复。可以推断出，如果交互器在第一次的询问中说了真话，答案就是 6。
- 接下来样例程序猜测 $ x=6 $，交互器给出 ":(" 的回复。发现答案并不是 6，说明交互器在第一次询问中说了谎。利用“交互器两次连续询问的回复必定有至少一个是真的”这个性质，我们可以推断出下一次询问交互器不能说谎。
- 接下来样例程序询问集合 $ \{1,2,3,4\} $，交互器给出 "NO" 的回复。由于交互器这次没有说谎，$ 1\sim6 $ 的整数中就只剩下 5 可能是 $ x $。
- 最终样例程序猜测 $ x=5 $，交互器给出 ":)" 的回复。**题目大意：** 这个问题是一个交互式问题。有一个隐藏的整数 $ x $ 满足 $ 1 \le x \le n $，你需要通过最多 53 次询问来找出这个 $ x $。每次询问你可以选择一个非空的整数集合 $ S $，然后询问 $ x $ 是否属于集合 $ S $。如果 $ x $ 属于 $ S $，你会得到回复 "YES"，否则得到 "NO"。但是，回答有可能是不真实的，我们只能保证在任意连续两次询问中至少有一次是真的。 除此之外，你还可以对 $ x $ 进行最多 2 次直接猜测。每次猜测后，如果猜对了，你会得到回复 ":)"，否则得到 ":("。一旦你得到了 ":)" 作为回答，你的程序就应该立即结束。 交互器在对 $ x $ 的直接猜测上不会说谎。如果你在某次猜测的前后各进行了一次询问，这两次询问的回复也至少有一个是真的。交互器是适应性的，即 $ x $ 的值可能会在交互过程中改变，但保证交互器的 $ x $ 总是满足上述询问限制。 **输入输出数据格式：** - **输入格式：** 输入的第一行包含一个整数 $ n $ ($ 1 \le n \le 10^5 $)，表示 $ x $ 的最大可能值。 - **输出格式：** 对于每次询问，如果你想询问一个集合 $ S $，首先输出字符 '?'，然后输出集合 $ S $ 的大小和集合 $ S $ 中的所有元素。每个元素应该是介于 $ 1 $ 和 $ n $ 之间的整数，且 $ S $ 中的元素必须互不相同。每次询问后，读取一个字符串 "YES" 或 "NO"，如题目所述。你可以进行最多 53 次这样的询问。 如果你想猜测 $ x $，首先输出字符 '!'，然后输出你的猜测。每次猜测后，读取 ":)" 或 ":("。如果你猜对了 $ x $，答案就是 ":)"，你的程序应该立即结束，否则你会得到 ":("。你可以进行最多 2 次这样的猜测。 在输出查询后不要忘记输出换行符并刷新输出缓冲区，否则你将得到超时错误。具体刷新方法根据使用的编程语言而异。 **样例解释：** 给定 $ n=6 $。 - 样例程序首先询问集合 $ \{1,2,5,4,3\} $，交互器给出 "NO" 的回复。可以推断出，如果交互器在第一次的询问中说了真话，答案就是 6。 - 接下来样例程序猜测 $ x=6 $，交互器给出 ":(" 的回复。发现答案并不是 6，说明交互器在第一次询问中说了谎。利用“交互器两次连续询问的回复必定有至少一个是真的”这个性质，我们可以推断出下一次询问交互器不能说谎。 - 接下来样例程序询问集合 $ \{1,2,3,4\} $，交互器给出 "NO" 的回复。由于交互器这次没有说谎，$ 1\sim6 $ 的整数中就只剩下 5 可能是 $ x $。 - 最终样例程序猜测 $ x=5 $，交互器给出 ":)" 的回复。