/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
(1,2,3,\ldots,2^{N}) の順列 P=(P_0,P_1,\ldots,P_{2^{N}-1}) が与えられます。
あなたは次の操作を何回でも(0 回でもよい)行うことができます。
- 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N} を満たす非負整数 a,b を選び、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
1 番目のテストケースにおいて、P に対して操作を一回も行わないとき、P=(1,2) となります。これは辞書順で最小の順列です。よって答えは(1,2) です。
2 番目のテストケースにおいて、a=1,b=1 を選んで操作を行うと P=(1,3,2,4) となります。P に対して何回操作を行っても (1,3,2,4) より辞書順で小さい順列を得られません。よって答えは (1,3,2,4) です。
3 番目のテストケースにおいて、以下の順番で操作を行うことで、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) です。
Score : 450 points
Problem Statement
You are given a permutation P=(P_0,P_1,\ldots,P_{2^{N}-1}) of (1,2,3,\ldots,2^{N}).
You can perform the following operation any number of times (possibly zero):
- Choose non-negative integers a,b satisfying 0 \leq a \times 2^{b} < (a+1) \times 2^{b} \leq 2^{N}, and reverse P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1}. Here, reversing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} means simultaneously replacing P_{a \times 2^{b}}, P_{a\times 2^{b}+1},\ldots,P_{(a+1) \times 2^{b}-1} with P_{(a+1) \times 2^{b}-1}, P_{(a+1) \times 2^{b}-2},\ldots,P_{a \times 2^{b}}.
Find the lexicographically smallest permutation P that can be obtained by repeating the operation.
You are given T test cases, so find the answer for each.
Constraints
- 1 \leq T \leq 10^{5}
- 1 \leq N \leq 18
- P is a permutation of (1,2,3,\ldots,2^{N}).
- For each input file, the sum of 2^N over all test cases is at most 3 \times 10^{5}.
- All input values are integers.
Input
The input is given from standard input in the following format:
T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T
\textrm{case}_i represents the i-th test case and is given in the following format:
N
P_0 P_1 \ldots P_{2^N-1}
Output
Output T lines. The i-th line (1 \leq i \leq T) should contain the answer to the i-th test case.
Sample Input 1
4 1 1 2 2 1 3 4 2 2 2 3 4 1 3 8 3 4 2 1 5 7 6
Sample Output 1
1 2 1 3 2 4 1 4 2 3 1 5 6 7 2 4 3 8
In the first test case, when no operation is performed on P, P=(1,2). This is the lexicographically smallest permutation. Thus, the answer is (1,2).
In the second test case, when we perform the operation with a=1,b=1, P becomes (1,3,2,4). No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,3,2,4). Thus, the answer is (1,3,2,4).
In the third test case, by performing operations in the following order, we can obtain P=(1,4,2,3):
- Perform the operation with a=0,b=1. P becomes (3,2,4,1).
- Perform the operation with a=0,b=2. P becomes (1,4,2,3).
No matter how many operations we perform on P, we cannot obtain a permutation lexicographically smaller than (1,4,2,3). Thus, the answer is (1,4,2,3).