/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
正整数 N が与えられます。
(1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) であって、 \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j を最小化するものを一つ求めてください。
ただし、 \displaystyle \bigoplus_{1\le j\le i} P_j は P_1,P_2,\ldots,P_i のビット単位 \mathrm{XOR} として定義されます。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。
- A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。
制約
- 1\le T\le 10^3
- 1\le N
- 全てのテストケースにおける N の総和は 2\times 10^5 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N
出力
各テストケースに対する答えを順に改行区切りで出力せよ。
各テストケースについて、\displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j を最小化する (1,2,\ldots,N) の順列 P=(P_1,P_2,\ldots,P_N) を空白区切りで出力せよ。
最小化する P が複数存在する場合、どれを出力しても正答となる。
入力例 1
3 3 1 7
出力例 1
1 3 2 1 4 5 3 2 6 7 1
1 番目のテストケースについて考えます。
P=(1,3,2) とすると、\displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j=1 + (1 \oplus 3) + (1 \oplus 3 \oplus 2) = 1+2+0=3 となります。
\displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j の値を 3 未満にすることはできないので、P=(1,3,2) を出力すると正答となります。
他にも P=(2,3,1) を出力しても正答となります。
Score : 500 points
Problem Statement
You are given a positive integer N.
Find one permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that minimizes \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j.
Here, \displaystyle \bigoplus_{1\le j\le i} P_j is defined as the bitwise \mathrm{XOR} of P_1,P_2,\ldots,P_i.
You are given T test cases; solve each of them.
What is bitwise \mathrm{XOR}?
The bitwise \mathrm{XOR} of non-negative integers A and B, A \oplus B, is defined as follows.
- In the binary representation of A \oplus B, the digit at the 2^k (k \geq 0) place is 1 if exactly one of the digits at the 2^k place in the binary representations of A and B is 1, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots, p_k.
Constraints
- 1\le T\le 10^3
- 1\le N
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N
Output
Output the answers for the test cases in order, separated by newlines.
For each test case, output a permutation P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N) that minimizes \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j, separated by spaces.
If there are multiple permutations P that achieve the minimum, any of them will be accepted.
Sample Input 1
3 3 1 7
Sample Output 1
1 3 2 1 4 5 3 2 6 7 1
Consider the first test case.
If P=(1,3,2), then \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j=1 + (1 \oplus 3) + (1 \oplus 3 \oplus 2) = 1+2+0=3.
The value of \displaystyle \sum_{i=1}^N \bigoplus_{1\le j\le i} P_j cannot be made less than 3, so outputting P=(1,3,2) is correct.
Outputting P=(2,3,1) is also correct.