2179D.md (2361B)
1 Source: https://codeforces.com/problemset/problem/2179/D 2 3 D. Blackslex and Penguin Civilization 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 Penguins are civilized creatures that communicate using permutations. Blackslex, as a penguin researcher, must study their means of communication. 22 23 For a given integer $n$, consider permutations$^{\text{∗}}$ $p$ of the array $[0, 1, \ldots, 2^n - 1]$. Define $$S(p) \;=\; \sum_{i=0}^{2^n-1} \operatorname{popcount}\!\bigl(p_0 \mathbin{\&} p_1 \mathbin{\&} \cdots \mathbin{\&} p_i\bigr),$$ where $\operatorname{popcount}(z)$ is the number of $1$-bits in the binary representation of $z$ (for instance, $\operatorname{popcount}(5) = 2$ because $5 = 101_2$ has two $1$-bits in the binary representation), and $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). . 24 25 A permutation is considered sacred if it maximizes $S(p)$. Find the lexicographically minimal$^{\text{†}}$ sacred permutation. 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{†}}$An array $a$ is lexicographically smaller than an array $b$ of the same size if and only if the following holds: 30 31 * in the first position where $a$ and $b$ differ, the array $a$ has a smaller element than the corresponding element in $b$. 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 16$) — the number of test cases. 36 37 Each test case contains a single integer $n$ ($1 \le n \le 16$). 38 39 It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{16}$. 40 41 Output 42 43 For each test case, output $2^n$ integers $p_0, p_1, \ldots, p_{2^n-1}$ — the required permutation. 44 45 Example 46 47 Input 48 49 ``` 50 2 51 52 1 53 54 2 55 ``` 56 57 Output 58 59 ``` 60 1 0 61 62 3 1 0 2 63 ``` 64 65 Note 66 67 For the first test case, there are two possible permutations. 68 69 * $p = [0, 1]$, $S(p) = 0$ 70 * $p = [1, 0]$, $S(p) = 1$ 71 72 For the second test case, $S([3, 1, 0, 2]) = 3$ is sacred. There are other permutations $p$ that are sacred, such as $p = [3, 2, 0, 1]$, but those are not lexicographically minimal.