2189C1.md (2207B)
1 Source: https://codeforces.com/problemset/problem/2189/C1 2 3 C1. XOR Convenience (Easy Version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is the easy version of the problem. The difference between the versions is that in this version, $2 \le i \le n-1$. Note that a correct solution for the hard version is not necessarily a correct solution for the easy version. 22 23 Given a natural number $n$. Find a permutation$^{\text{∗}}$ $p$ of length $n$, such that for each $i$ ($\style{color:red}{2 \le i \le n-1}$) there exists a $j$ ($\style{color:red}{i \le j \le n}$) such that $p_i = p_j \oplus i$ $^{\text{†}}$. 24 25 It can be proven that under the constraints of the problem, there exists at least one suitable permutation $p$. 26 27 $^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 28 29 $^{\text{†}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 34 35 The only line of each test case contains a single integer $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the permutation. 36 37 It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$. 38 39 Output 40 41 For each test case, output $n$ integers $p_1,p_2,\ldots,p_n$ — the permutation $p$. 42 43 If there are multiple solutions, you may output any of them. 44 45 Example 46 47 Input 48 49 ``` 50 2 51 52 3 53 54 6 55 ``` 56 57 Output 58 59 ``` 60 2 1 3 61 3 6 2 5 1 4 62 ``` 63 64 Note 65 66 In the first test case, the permutation $p = [2,1,3]$ is suitable since $p_2 = 1$ and $p_3 \oplus 2 = 1$. 67 68 In the second test case, the permutation $p = [3,6,2,5,1,4]$ is suitable, as: 69 70 * $p_2 = 6 = 4 \oplus 2 = p_6 \oplus 2$ 71 * $p_3 = 2 = 1 \oplus 3 = p_5 \oplus 3$ 72 * $p_4 = 5 = 1 \oplus 4 = p_5 \oplus 4$ 73 * $p_5 = 1 = 4 \oplus 5 = p_6 \oplus 5$