codeforces-scrape

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

1722G.md (1246B)


      1 Source: https://codeforces.com/problemset/problem/1722/G
      2 
      3 G. Even-Odd XOR
      4 
      5 time limit per test
      6 
      7 1 second
      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 Given an integer $n$, find any array $a$ of $n$ distinct nonnegative integers less than $2^{31}$ such that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of the elements on odd indices equals the bitwise XOR of the elements on even indices.
     22 
     23 Input
     24 
     25 The first line of the input contains an integer $t$ ($1 \leq t \leq 629$) — the number of test cases.
     26 
     27 Then $t$ lines follow, each containing a single integer $n$ $(3 \leq n \leq 2\cdot10^5)$ — the length of the array.
     28 
     29 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.
     30 
     31 Output
     32 
     33 For each test case, output one line containing $n$ distinct integers that satisfy the conditions.
     34 
     35 If there are multiple answers, you can output any of them.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 7
     43 8
     44 3
     45 4
     46 5
     47 6
     48 7
     49 9
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 4 2 1 5 0 6 7 3
     56 2 1 3
     57 2 1 3 0
     58 2 0 4 5 3
     59 4 1 2 12 3 8
     60 1 2 3 4 5 6 7
     61 8 2 3 7 4 0 5 6 9
     62 ```
     63 
     64 Note
     65 
     66 In the first test case the XOR on odd indices is $4 \oplus 1 \oplus 0 \oplus 7 = 2$ and the XOR on even indices is $2 \oplus 5 \oplus 6 \oplus 3= 2$.