codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.