2072C.md (1963B)
1 Source: https://codeforces.com/problemset/problem/2072/C 2 3 C. Creating Keys for StORages Has Become My Main Skill 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 Akito still has nowhere to live, and the price for a small room is everywhere. For this reason, Akito decided to get a job at a bank as a key creator for storages. 22 23 In this magical world, everything is different. For example, the key for a storage with the code $(n, x)$ is an array $a$ of length $n$ such that: 24 25 * $a_1 \ | \ a_2 \ | \ a_3 \ | \ \ldots \ | \ a_n = x$, where $a \ | \ b$ is the [bitwise "OR"](https://en.wikipedia.org/wiki/Bitwise_operation#OR) of numbers $a$ and $b$. 26 * $\text{MEX}(\{ a_1, a_2, a_3, \ldots, a_n \})$$^{\text{∗}}$ is maximized among all such arrays. 27 28 Akito diligently performed his job for several hours, but suddenly he got a headache. Substitute for him for an hour; for the given $n$ and $x$, create any key for the storage with the code $(n, x)$. 29 30 $^{\text{∗}}$$\text{MEX}(S)$ is the minimum non-negative integer $z$ such that $z$ is not contained in the set $S$ and all $0 \le y \lt z$ are contained in $S$. 31 32 Input 33 34 The first line contains the number $t$ ($1 \le t \le 10^4$) — the number of test cases. 35 36 In the only line of each test case, two numbers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5, 0 \le x \lt 2^{30}$) are given — the length of the array and the desired value of the bitwise "OR". 37 38 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, output $n$ integers $a_i$ ($0 \le a_i \lt 2^{30}$) — the elements of the key array that satisfy all the conditions. 43 44 If there are multiple suitable arrays, output any of them. 45 46 Example 47 48 Input 49 50 ``` 51 9 52 53 1 69 54 55 7 7 56 57 5 7 58 59 7 3 60 61 8 7 62 63 3 52 64 65 9 11 66 67 6 15 68 69 2 3 70 ``` 71 72 Output 73 74 ``` 75 69 76 6 0 3 4 1 2 5 77 4 1 3 0 2 78 0 1 2 3 2 1 0 79 7 0 6 1 5 2 4 3 80 0 52 0 81 0 1 8 3 0 9 11 2 10 82 4 0 3 8 1 2 83 0 3 84 ```