P12580 [UOI 2021] 猜排列【交互题暂未配置】

请注意本题不寻常的时间限制。 给定一个由 $n$ 个数字组成的排列（$n$ 是 2 的幂次）。排列中元素的顺序对你来说是未知的。 排列是指长度为 $n$ 的整数序列，包含从 $1$ 到 $n$ 的所有数字，每个数字恰好出现一次。例如，$[1]$、$[4, 3, 5, 1, 2]$、$[3, 2, 1]$ 是排列，而 $[1, 1]$、$[4, 3, 1]$、$[2, 3, 4]$ 不是。 此外，存在一种查询方式：你可以提供一个长度为 $n$ 的数组 $a$，满足 $1 \le a_i \le n$（注意 $a$ 不一定是排列）。作为响应，你会得到一个长度为 $n$ 的数组 $c$，其生成规则如下： ``` c = 长度为 n 的全零数组 for i = 1 to n: if p[a[i]] > p[i]: c[a[i]] += 1 返回 c ``` 你的任务是找出隐藏的排列 $p$。最大查询次数请参见“评分”部分。

第一行包含两个整数 $t$ 和 $q$（$1 \le t, q \le 256$）——分别是测试用例的数量和每个测试用例允许的最大查询次数。 ### 交互说明 对于每个测试用例，首先读取一个整数 $n$（$1 \le n \le 1024$），表示排列 $p$ 的长度。 保证 $n$ 是 2 的幂次（即存在非负整数 $k$ 使得 $2^k = n$）。 要发起查询，请输出 $1\ a_1\ a_2 \dots \ a_n$（$1 \le a_i \le n$）。 作为响应，评测系统会返回数组 $c$，其生成规则如题目描述所示，格式为 $c_1\ c_2\ \dots \ c_n$。 发起查询后，请确保输出换行符并刷新输出缓冲区，否则可能触发“超出时间限制”错误。刷新缓冲区的方法如下： - C++：`fflush(stdout)` 或 `cout.flush()`； - Java：`System.out.flush()`； - Pascal：`flush(output)`； - Python：`stdout.flush()`； 其他语言请参考相关文档。 注意：如果你的查询无效（超过查询次数限制或数组 $a$ 不满足条件），评测系统会返回 $-1$ 并终止程序。如果读取到 $-1$，请立即终止程序以避免意外结果。 当你确定排列 $p$ 后，请输出 $2\ p_1\ p_2 \dots \ p_n$。 如果是最后一个测试用例，程序应终止；否则继续处理下一个测试用例。

见交互说明。

### 说明 从第一次查询可知 $p_1 < p_3 < p_4 < p_2$。 因此，所求排列为 $[1, 4, 2, 3]$。 ### 评分 $q$ 表示程序允许的最大查询次数。 - （3 分）$n \le 16$，$q=256$，$t=128$； - （7 分）$n \le 32$，$q=256$，$t=128$； - （8 分）$n \le 256$，$q=256$，$t=128$； - （14 分）$n \le 512$，$q=256$，$t=128$； - （20 分）$n \le 512$，$q=128$，$t=256$； - （最高 48 分）$n \le 1024$，$q=127$，$t=256$；设 $k$ 为单个测试用例中实际使用的最大查询次数，则得分规则为： - 若 $k > 127$，得 0 分； - 若 $55 < k \le 127$，得 $48 - \lceil \frac{24(k-55)}{37} \rceil$ 分； - 若 $k \le 55$，得 48 分； 翻译由 DeepSeek V3 完成