2035C.md (2432B)
1 Source: https://codeforces.com/problemset/problem/2035/C 2 3 C. Alya and Permutation 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 Alya has been given a hard problem. Unfortunately, she is too busy running for student council. Please solve this problem for her. 22 23 Given an integer $n$, construct a permutation $p$ of integers $1, 2, \ldots, n$ that maximizes the value of $k$ (which is initially $0$) after the following process. 24 25 Perform $n$ operations, on the $i$-th operation ($i=1, 2, \dots, n$), 26 27 * If $i$ is odd, $k=k\,\&\,p_i$, where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). 28 * If $i$ is even, $k=k\,|\,p_i$, where $|$ denotes the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). 29 30 Input 31 32 The first line contains a single integer $t$ ($1\le t\le 500$) — the number of test cases. 33 34 The only line of each test case contains a single integer $n$ ($5\le n\le 2 \cdot 10^5$) — the length of the permutation. 35 36 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 37 38 Output 39 40 For each test case, output the maximum value of $k$ in the first line and output the permutation $p_1, p_2,\ldots, p_n$ in the second line. 41 42 If there are multiple such permutations, output any. 43 44 Example 45 46 Input 47 48 ``` 49 6 50 51 5 52 53 6 54 55 7 56 57 8 58 59 9 60 61 10 62 ``` 63 64 Output 65 66 ``` 67 5 68 2 1 3 4 5 69 7 70 1 2 4 6 5 3 71 7 72 2 4 5 1 3 6 7 73 15 74 2 4 5 1 3 6 7 8 75 9 76 2 4 5 6 7 1 3 8 9 77 15 78 1 2 3 4 5 6 8 10 9 7 79 ``` 80 81 Note 82 83 For the first test case, the value of $k$ is determined as follows: 84 85 $k = 0$ initially. 86 87 * On the $1$st operation, $1$ is odd, so Alya sets $k$ to be $k\&p_1 = 0\&2 = 0$. 88 * On the $2$nd operation, $2$ is even, so Alya sets $k$ to be $k|p_2 = 0|1 = 1$. 89 * On the $3$rd operation, $3$ is odd, so Alya sets $k$ to be $k\&p_3 = 1\&3 = 1$. 90 * On the $4$th operation, $4$ is even, so Alya sets $k$ to be $k|p_4 = 1|4 = 5$. 91 * On the $5$th operation, $5$ is odd, so Alya sets $k$ to be $k\&p_5 = 5\&5 = 5$. 92 93 The final value of $k$ is $5$. It can be shown that the final value of $k$ is at most $5$ for all permutations of length $5$. Another valid output is $[2, 3, 1, 4, 5]$. 94 95 For the second test case, the final value of $k$ is $7$. It can be shown that the final value of $k$ is at most $7$ for all permutations of length $6$. Other valid outputs include $[2, 4, 1, 6, 3, 5]$ and $[5, 2, 6, 1, 3, 4]$.