CF2129C3.Interactive RBS (Hard Version)

这是一个交互题。

这是该题的困难版本。唯一的区别在于查询次数的限制。只有在所有版本都被解决后，才能进行 Hack。

有一个长度为 $n$ 的隐藏括号序列 $s$，其中 $s$ 只包含 $\texttt{'('}$ 和 $\texttt{')'}$。保证 $s$ 至少包含一个 $\texttt{'('}$ 和一个 $\texttt{')'}$。

你可以通过询问来找出这个括号序列。每次询问的形式如下：你选择一个整数 $k$ 和任意的下标 $i_1, i_2, \ldots, i_k$（$1 \le k \le 1000$，$1 \le i_1, i_2, \ldots, i_k \le n$）。注意下标可以相同。接下来，你会收到一个由评测器计算的整数 $f(s_{i_1}s_{i_2}\ldots s_{i_k})$。

对于一个括号序列 $t$，$f(t)$ 表示 $t$ 中非空的正规括号子串的数量（子串必须是连续的）。例如，$f(\texttt{"()())"}) = 3$。

一个括号序列被称为正规括号序列，当且仅当它可以通过以下方式构造：

1. 空序列 $\varnothing$ 是正规括号序列。
2. 如果括号序列 $A$ 是正规括号序列，则 $\mathtt{(}A\mathtt{)}$ 也是正规括号序列。
3. 如果括号序列 $A$ 和 $B$ 都是正规括号序列，则它们的连接 $AB$ 也是正规括号序列。

例如，序列 $\texttt{"(())()"}$、$\texttt{"()"}$ 是正规括号序列，而 $\texttt{"(()"}$ 和 $\texttt{"())("}$ 不是。

请在不超过 $100$ 次查询内找出序列 $s$。

每个测试包含多组测试数据。第一行包含测试组数 $t$（$1 \le t \le 20$）。每组测试数据的描述如下。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 1000$）。此时，括号序列 $s$ 已经被选定。本题的交互器是非自适应的。也就是说，每组测试数据中的括号序列 $s$ 是固定的，在交互过程中不会改变。

每次询问，你需要选择一个整数 $k$ 和任意的下标 $i_1, i_2, \ldots, i_k$（$1 \le k \le 1000$，$1 \le i_1, i_2, \ldots, i_k \le n$），并输出如下格式的一行（不含引号）：

• “$?\ k\ i_1\ i_2\ \ldots\ i_k$”

之后，你会收到一个整数 $f(s_{i_1}s_{i_2}\ldots s_{i_k})$。

你最多可以进行 $100$ 次这样的查询。

接下来，如果你的程序已经找到了括号序列 $s$，请输出一行，格式如下（不含引号）：

• “$!\ s_1s_2\ldots s_n$”

注意，这一行不计入查询次数。

之后，进入下一组测试数据。

如果在一次交互中你的查询次数超过 $100$，你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，你的程序会因为继续从已关闭的流中读取而收到任意判定。

每次输出查询或答案后，别忘了输出换行并刷新输出缓冲区，否则会收到 Idleness Limit Exceeded 判定。具体做法如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其它语言请查阅相关文档。

Hack

Hack 时请按照以下格式输入测试数据。

第一行包含测试组数 $t$（$1 \le t \le 20$）。每组测试数据的描述如下。

每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 1000$）。

每组测试数据的第二行包含一个括号序列 $s_1 s_2\ldots s_n$，其中 $s_i = \texttt{'('}$ 或 $s_i = \texttt{')'}$。

括号序列 $s$ 必须至少包含一个 $\texttt{'('}$ 和一个 $\texttt{')'}$。

在第一个测试用例中，隐藏的括号序列为 $s=\texttt{")(("}$。

对于查询 “? 4 1 2 3 3”，评测器返回 $0$，因为 $f(s_{1}s_{2}s_{3}s_{3}) = f(\texttt{")((("}) = 0$。

对于查询 “? 2 2 1”，评测器返回 $1$，因为 $f(s_{2}s_{1}) = f(\texttt{"()"}) = 1$。

对于查询 “? 2 3 1”，评测器返回 $1$，因为 $f(s_{3}s_{1}) = f(\texttt{"()"}) = 1$。

在第二个测试用例中，隐藏的括号序列为 $s=\texttt{"()"}$。

对于查询 “? 4 1 2 1 2”，评测器返回 $3$，因为 $f(s_{1}s_{2}s_{1}s_{2}) = f(\texttt{"()()"}) = 3$。

注意，样例仅用于帮助理解题意，并不保证一定能唯一确定括号序列 $s$。

由 ChatGPT 4.1 翻译