codeforces-scrape

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

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 ```