codeforces-scrape

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

2175B.md (1847B)


      1 Source: https://codeforces.com/problemset/problem/2175/B
      2 
      3 B. XOR Array
      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 You are given three integers $n$, $l$, and $r$.
     22 
     23 You need to generate an array $a$ of positive ($1 \leq a_i \leq 10^9$) integers of length $n$. Let $f(x, y)$, for $1 \le x \le y \le n$, be the bitwise XOR$^{\text{∗}}$ value $a_x \oplus a_{x+1} \oplus \ldots \oplus a_y$. You need to make sure that $$\begin{cases} f(x, y) = 0\quad \text{when }x = l\text{ and }y = r; \text{and}\\ f(x, y) \ne 0\quad \text{when }x \ne l \text{ or } y \ne r. \end{cases}$$
     24 
     25 $^{\text{∗}}$$\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 The only line of each test case contains three integers $n$, $l$, and $r$ ($2 \leq n \leq 4\cdot 10^5$, $1 \leq l \lt r \leq n$).
     32 
     33 It is guaranteed that the sum of $n$ across all test cases does not exceed $5\cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, print a single line containing $n$ integers $a_1, a_2, \ldots a_n$.
     38 
     39 We can show that an answer always exists. If there are multiple solutions, print any of them.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 4
     47 
     48 3 1 3
     49 
     50 4 1 3
     51 
     52 8 2 4
     53 
     54 4 3 4
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 9 8 1 
     61 2 7 5 4 
     62 9 1 9 8 10 5 4 9
     63 85484 130377 6031 6031
     64 ```
     65 
     66 Note
     67 
     68 In the first test case, $f(1, 3) = 9 \oplus 8 \oplus 1 = 0$, while all other non-empty subarrays have non-zero bitwise XOR:
     69 
     70 * $f(1, 2) = 9 \oplus 8 = 1 \ne 0$,
     71 * $f(2, 3) = 8 \oplus 1 = 9 \ne 0$,
     72 * $f(1, 1) = 9 \ne 0$,
     73 * $f(2, 2) = 8 \ne 0$,
     74 * $f(3, 3) = 1 \ne 0$.
     75 
     76 In the second test case, $2 \oplus 7 \oplus 5 = 0$, while, for example, $7 \oplus 5 \oplus 4 = 6 \ne 0$.