分数: 450 点
问题陈述
给你一个排列 P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).
您可以执行以下操作任意次数(可能为零):
- 选择非负整数 a,b 满意 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N},并反转 P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}。在这里,倒车 P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} 表示同时更换 P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} 与 P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.
找到字典顺序最小的排列 重复操作即可得到 P 。
你被给予 T 测试用例,因此找到每个用例的答案。
约束
- 1 \leq T \leq 10^{5}
- 1 \leq N \leq 18
- P 是一个排列 (1,2,3,\ldots,2^{N}).
- 对于每个输入文件,总和 2^N 所有测试用例最多 3 \times 10^{5}.
- 所有输入值均为整数。
输入
输入由标准输入给出,格式如下:
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i 代表 i-第一个测试用例,以以下格式给出:
N
P_0 P_1 \ldots P_{2^N-1}
输出
输出 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
4 1 1 2 2 1 3 4 2 2 2 3 4 1 3 8 3 4 2 1 5 7 6
示例输出 1
1 2 1 3 2 4 1 4 2 3 1 5 6 7 2 4 3 8
在第一个测试用例中,当不执行任何操作时 P, P=(1,2)。这是字典顺序上最小的排列。因此,答案是 (1,2).
在第二个测试用例中,当我们执行操作时 a=1,b=1, P 变为 (1,3,2,4)。无论我们执行多少操作 P,我们无法获得按字典顺序小于的排列 (1,3,2,4)。因此,答案是 (1,3,2,4).
在第三个测试用例中,通过按以下顺序执行操作,我们可以得到 P=(1,4,2,3):
- 执行操作 a=0,b=1. P 变为 (3,2,4,1).
- 执行操作 a=0,b=2. P 变为 (1,4,2,3).
无论我们执行多少次操作 P,我们无法获得按字典顺序小于的排列 (1,4,2,3)。因此,答案是 (1,4,2,3).