Too Many Impostors (hard version)

题意翻译

**这是一道交互题。** **本题与 [CF1617D1](https://www.luogu.com.cn/problem/CF1617D1) 的唯一区别在于最多可询问的次数。** 有 $n$ 个玩家把号为 $1$ 到 $n$，这当中有 $k$ 个坏人和 $n-k$ 个好人，你只知道 $\frac n3<k<\frac{2n}3$，并不知道 $k$ 的值。你需要找到 $k$ 的值和所有 $k$ 个坏人的玩家编号，而唯一的方法就是进行若干次询问。 在每次询问中，你可以指定三个玩家的编号 $a,b,c$，并希望知道这三个玩家当中是好人比坏人多还是坏人比好人多。你将得到一个整数 $r$ 作为回答。如果 $r=0$，那么坏人比好人多，否则好人比坏人多。 现在，请你通过最多 $n+6$ 次询问求出 $k$ 的值和所有 $k$ 个坏人的玩家编号。 **交互方式：** 在交互开始时，你需要读入一个正整数 $t$，表示数据组数。 对于每组数据，首先读入一个正整数 $n$，表示玩家个数。 随后你可以开始进行最多 $n+6$ 次询问，输出每次询问的格式为 `? a b c`，需要满足 $1\leqslant a,b,c\leqslant n$ 且 $a,b,c$ 互不相同。 每次询问之后，你需要读入一个整数 $r$。其中： - $r=0$ 表示坏人比好人多； - $r=1$ 表示好人比坏人多； - $r=-1$ 表示你刚刚进行了一次非法询问或者询问次数已经超过限制，此时请立即退出程序，否则你可能会随机 WA/TLE/RE。 在若干次询问之后，如果你已经知道 $k$ 的值和所有 $k$ 个坏人的玩家编号，请先输出 `! `（**后面有空格**），随后输出 $k$ 和所有 $k$ 个坏人的玩家编号，以空格为间隔。随后请立即进入下一组数据，如果没有下一组数据则结束程序。 请注意输出每一行之后需要刷新缓冲区，否则你将无法通过此题。部分常用语言刷新缓冲区的方式如下表所示： | 语言 | 方式 | | :----------: | :----------: | | C++ | `fflush(stdout)` 或 `cout.flush()` | | Java | `System.out.flush()` | | Pascal | `flush(output)` | | Python | `stdout.flush()` | 对于其他语言，请自行查阅相关文献。 数据范围： - $1\leqslant t\leqslant 100$。 - $6\leqslant n\leqslant 10^4$，$\sum n\leqslant 2\times 10^4$。 - **保证 $n$ 是 $3$ 的倍数**。 Translated by Eason_AC 2021.12.17

题目描述

This is an interactive problem. The only difference between the easy and hard version is the limit on number of questions. There are $ n $ players labelled from $ 1 $ to $ n $ . It is guaranteed that $ n $ is a multiple of $ 3 $ . Among them, there are $ k $ impostors and $ n-k $ crewmates. The number of impostors, $ k $ , is not given to you. It is guaranteed that $ \frac{n}{3} < k < \frac{2n}{3} $ . In each question, you can choose three distinct integers $ a $ , $ b $ , $ c $ ( $ 1 \le a, b, c \le n $ ) and ask: "Among the players labelled $ a $ , $ b $ and $ c $ , are there more impostors or more crewmates?" You will be given the integer $ 0 $ if there are more impostors than crewmates, and $ 1 $ otherwise. Find the number of impostors $ k $ and the indices of players that are impostors after asking at most $ n+6 $ questions. The jury is adaptive, which means the indices of impostors may not be fixed beforehand and can depend on your questions. It is guaranteed that there is at least one set of impostors which fulfills the constraints and the answers to your questions at any time.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). Description of the test cases follows. The first and only line of each test case contains a single integer $ n $ ( $ 6 \le n < 10^4 $ , $ n $ is a multiple of $ 3 $ ) — the number of players. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^4 $ .

输出格式

For each test case, the interaction starts with reading $ n $ . Then you are allowed to make at most $ n+6 $ questions in the following way: "? a b c" ( $ 1 \le a, b, c \le n $ , $ a $ , $ b $ and $ c $ are pairwise distinct). After each one, you should read an integer $ r $ , which is equal to $ 0 $ if there are more impostors than crewmates among players labelled $ a $ , $ b $ and $ c $ , and equal to $ 1 $ otherwise. Answer $ -1 $ instead of $ 0 $ or $ 1 $ means that you made an invalid query. Exit immediately after receiving $ -1 $ and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream. When you have found the indices of all impostors, print a single line "! " (without quotes), followed by the number of impostors $ k $ , followed by $ k $ integers representing the indices of the impostors. Please note that you must print all this information on the same line. After printing the answer, your program must then continue to solve the remaining test cases, or exit if all test cases have been solved. After printing the queries and answers do not forget to output end of line and flush the output buffer. Otherwise, you will get the Idleness limit exceeded verdict. To do flush use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - Read documentation for other languages. Hacks You cannot make hacks in this problem.

输入输出样例

输入样例 #1

2
6

0

1

9

1

输出样例 #1

? 1 2 3

? 3 4 5

! 3 4 1 2

? 7 1 9

! 4 2 3 6 8

说明

Explanation for example interaction (note that this example only exists to demonstrate the interaction procedure and does not provide any hint for the solution): For the first test case: Question "? 1 2 3" returns $ 0 $ , so there are more impostors than crewmates among players $ 1 $ , $ 2 $ and $ 3 $ . Question "? 3 4 5" returns $ 1 $ , so there are more crewmates than impostors among players $ 3 $ , $ 4 $ and $ 5 $ . Outputting "! 3 4 1 2" means that one has found all the impostors, by some miracle. There are $ k = 3 $ impostors. The players who are impostors are players $ 4 $ , $ 1 $ and $ 2 $ . For the second test case: Question "? 7 1 9" returns $ 1 $ , so there are more crewmates than impostors among players $ 7 $ , $ 1 $ and $ 9 $ . Outputting "! 4 2 3 6 8" means that one has found all the impostors, by some miracle. There are $ k = 4 $ impostors. The players who are impostors are players $ 2 $ , $ 3 $ , $ 6 $ and $ 8 $ .