/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
正整数 N が与えられます。
以下の条件をすべて満たすような非負整数列 P=(P_1, P_2, \dots,P_N), A=(A_1, A_2, \dots,A_N) を 1 つ出力してください。
- 0 \leq P_i < 2^{30}~(1 \leq i \leq N)
- 0 \leq A_i < 2^{30}~(1 \leq i \leq N)
- (P_1~\mathrm{OR}~A_i, P_2~\mathrm{OR}~A_i, \dots, P_N~\mathrm{OR}~A_i) の最長狭義単調増加部分列の長さは i である。(1 \leq i \leq N)
- \mathrm{OR} はビット単位 \mathrm{OR} 演算を表します。
この問題の制約下で、条件を満たす P, A が 1 つ以上存在することが証明できます。
1 つの入力につき、T 個のテストケースを解いてください。
ビット単位 \mathrm{OR} 演算とは
非負整数 A, B のビット単位 \mathrm{OR}、A\ \mathrm{OR}\ B は以下のように定義されます。
- A\ \mathrm{OR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち少なくとも片方が 1 であれば 1、そうでなければ 0 である。
制約
- 1 \leq T
- 1 \leq N \leq 1024
- 1 つの入力に含まれるテストケースについて、N の総和は 200000 以下
- 1 つの入力に含まれるテストケースについて、N^2 の総和は 1024^2 以下
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各ケースは以下の形式で与えられる。
N
出力
t 番目に \mathrm{case}_t に対する答えを出力せよ。
各ケースについて、以下の形式に従って答えを出力せよ。
P_1 P_2 \ldots P_N A_1 A_2 \ldots A_N
答えが複数存在する場合、どれを出力しても正解となる。
入力例 1
3 3 8 1
出力例 1
3 14 5 13 2 10 6 902 909 186 684 219 471 248 1023 249 64 0 264 768 778 794 2025 1026
1 番目のテストケースについて、出力例は P = (3, 14, 5), A = (13, 2, 10) です。
- (3~\mathrm{OR}~13, 14~\mathrm{OR}~13, 5~\mathrm{OR}~13) = (15, 15, 13) の最長狭義単調増加部分列の 1 つは (13) であり、その長さは 1 です。
- (3~\mathrm{OR}~2, 14~\mathrm{OR}~2, 5~\mathrm{OR}~2) = (3, 14, 7) の最長狭義単調増加部分列の 1 つは (3, 7) であり、その長さは 2 です。
- (3~\mathrm{OR}~10, 14~\mathrm{OR}~10, 5~\mathrm{OR}~10) = (11, 14, 15) の最長狭義単調増加部分列の 1 つは (11, 14, 15) であり、その長さは 3 です。
上記より、P = (3, 14, 5), A = (13, 2, 10) は条件を満たすことが確認できます。
Score : 900 points
Problem Statement
You are given a positive integer N.
Output one pair of non-negative integer sequences P=(P_1, P_2, \dots,P_N), A=(A_1, A_2, \dots,A_N) that satisfies all of the following conditions:
- 0 \leq P_i < 2^{30}~(1 \leq i \leq N)
- 0 \leq A_i < 2^{30}~(1 \leq i \leq N)
- The length of a longest strictly increasing subsequence of (P_1~\mathrm{OR}~A_i, P_2~\mathrm{OR}~A_i, \dots, P_N~\mathrm{OR}~A_i) is i. (1 \leq i \leq N)
- \mathrm{OR} denotes the bitwise \mathrm{OR} operation.
It can be proved that under the constraints of this problem, there exists at least one pair P, A that satisfies the conditions.
Solve T test cases per input.
What is bitwise \mathrm{OR}?
The bitwise \mathrm{OR} of non-negative integers A, B, denoted A\ \mathrm{OR}\ B, is defined as follows:
- When A\ \mathrm{OR}\ B is written in binary, the digit at position 2^k (k \geq 0) is 1 if at least one of the digits at position 2^k in the binary representations of A and B is 1, and 0 otherwise.
Constraints
- 1 \leq T
- 1 \leq N \leq 1024
- For test cases in a single input, the sum of N is at most 200000.
- For test cases in a single input, the sum of N^2 is at most 1024^2.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each case is given in the following format:
N
Output
Output a solution for \mathrm{case}_1, \mathrm{case}_2, \dots, \mathrm{case}_T in this order.
For each case, output the answer in the following format:
P_1 P_2 \ldots P_N A_1 A_2 \ldots A_N
If there are multiple solutions, any of them will be considered correct.
Sample Input 1
3 3 8 1
Sample Output 1
3 14 5 13 2 10 6 902 909 186 684 219 471 248 1023 249 64 0 264 768 778 794 2025 1026
For the first test case, the sample output is P = (3, 14, 5), A = (13, 2, 10).
- One longest strictly increasing subsequence of (3~\mathrm{OR}~13, 14~\mathrm{OR}~13, 5~\mathrm{OR}~13) = (15, 15, 13) is (13), whose length is 1.
- One longest strictly increasing subsequence of (3~\mathrm{OR}~2, 14~\mathrm{OR}~2, 5~\mathrm{OR}~2) = (3, 14, 7) is (3, 7), whose length is 2.
- One longest strictly increasing subsequence of (3~\mathrm{OR}~10, 14~\mathrm{OR}~10, 5~\mathrm{OR}~10) = (11, 14, 15) is (11, 14, 15), whose length is 3.
From the above, it can be confirmed that P = (3, 14, 5), A = (13, 2, 10) satisfies the conditions.