AT_utpc2024_h Hidden Sequence Rotation

本题为**交互式问题**（你的程序将与评测程序通过标准输入输出进行交互）。 给定一个整数 $N$。评测程序隐藏了一个长度为 $N$ 的序列 $A = (A_0, \dots, A_{N-1})$，其中每个元素是 $1$ 到 $10^5$ 之间的整数。请注意，下标从 $0$ 开始。 对于整数 $s=0,\dots,N-1$ 与 $l=1,\dots,N$，定义序列 $A(s, l)$： - 这是一个长度为 $l$ 的序列，第 $i=0,\dots,l-1$ 项为 $A_{(s+i) \bmod N}$。 你可以最多进行 $20$ 次如下格式的询问： - 你需要输出一个由整数对组成的序列 $((s_0,l_0),\dots,(s_{k-1},l_{k-1}))$，且满足 - $1 \leq k \leq N$ - $0 \leq s_i < N$ - $1 \leq l_i \leq N$ - $\sum_{i = 0}^{k - 1} l_i \leq N$ - 对于你的询问，评测程序会返回 $i = 0, \dots, k - 1$ 中所有使得 $A(s_i, l_i)$ 字典序最小的 $i$。即，设 $A_{\mathrm{tmpmin}} = \min_{0 \leq i < k} A(s_i, l_i)$，那么返回集合 $\{i_0, \dots, i_{k'-1}\} \coloneqq \{i \mid 0 \leq i < k, \, A(s_i, l_i) = A_{\mathrm{tmpmin}}\}$。 请通过上述操作，找出所有 $s = 0, \dots, N-1$ 使得 $A(s, N)$ 的字典序最小。即找到集合 $\{s_0, \dots, s_{n-1}\} \coloneqq \{s \mid 0 \leq s < N,\; A(s, N) = A_{\mathrm{min}}\}$，其中 $A_{\mathrm{min}} = \min_{0 \leq s < N} A(s, N)$。

本题为交互式问题（你的程序需通过标准输入输出与评测程序交互）。 首先，从标准输入读取 $N$。 ``` N ``` 此后，你可以进行询问，每次按下述格式输出： ``` ? k s_0 l_0 s_1 l_1 ... s_{k-1} l_{k-1} ``` 你的输出必须遵循题目的询问约束条件。 如果查询格式正确，评测程序会以如下格式返回本次询问的结果： ``` k' i_0 i_1 ... i_{k'-1} ``` 且 $0 \le i_0 < \dots < i_{k'-1} < k$。 如果查询格式错误、询问次数超过20次或其它非法情况，评测程序会返回 `-1`： ``` -1 ``` 收到 `-1` 时，程序应立即退出。 当你得出答案后，请按如下格式输出： ``` ! n s_0 s_1 ... s_{n-1} ``` 其中 $s_i$ 需为 $0$ 到 $N-1$ 之间互不相同的整数。

见上文，需按题面所述格式进行标准输出。

**注意事项** - **每次输出到标准输出后，请务必刷新输出流。否则有可能因输出未及时被评测程序收到而导致 TLE。** - 若你输出不合法、格式错误，或程序异常退出，判题结果不确定。 - 输出最终答案后（或收到 `-1`），请立即正常退出程序。否则，判题结果不确定。 - 注意不要输出多余的换行，否则也会被认定为格式错误。 - 序列 $A$ 在整个交互过程中固定不变，不会根据你的询问自适应修改。 **输入输出样例** 以 $N=6$，$A=(1, 2, 3, 1, 2, 4)$ 为例： 输入 输出 说明 6 ? 3 0 1 1 1 3 1 查询 $A(0, 1) = (1), A(1, 1) = (2), A(3, 1) = (1)$ 2 0 2 $0$ 和 $2$ 号是最小的 ? 2 0 3 3 3 查询 $A(0, 3) = (1, 2, 3), A(3, 3) = (1, 2, 4)$ 1 0 只有第 $0$ 号最小 ! 1 0 $A(s, N)$ 字典序最小的 $s$ 只有 $0$，输出结果 # 提示 - 所有输入均为整数。 - $1 \leq N \leq 10^5$。 由 ChatGPT 5 翻译