codeforces-scrape

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

1658D1.md (2073B)


      1 Source: https://codeforces.com/problemset/problem/1658/D1
      2 
      3 D1. 388535 (Easy Version)
      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 This is the easy version of the problem. The difference in the constraints between both versions is colored below in red. You can make hacks only if all versions of the problem are solved.
     22 
     23 Marin and Gojou are playing hide-and-seek with an array.
     24 
     25 Gojou initially performs the following steps:
     26 
     27 * First, Gojou chooses $2$ integers $l$ and $r$ such that $l \leq r$.
     28 * Then, Gojou makes an array $a$ of length $r-l+1$ which is a permutation of the array $[l,l+1,\ldots,r]$.
     29 * Finally, Gojou chooses a secret integer $x$ and sets $a_i$ to $a_i \oplus x$ for all $i$ (where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)).
     30 
     31 Marin is then given the values of $l,r$ and the final array $a$. She needs to find the secret integer $x$ to win. Can you help her?
     32 
     33 Note that there may be multiple possible $x$ that Gojou could have chosen. Marin can find any possible $x$ that could have resulted in the final value of $a$.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \leq t \leq 10^5$) — the number of test cases.
     38 
     39 In the first line of each test case contains two integers $l$ and $r$ ($ \color{red}{\boldsymbol{0} \boldsymbol{=} \boldsymbol{l}} \le r \lt 2^{17}$).
     40 
     41 The second line contains $r - l + 1$ integers of $a_1,a_2,\ldots,a_{r-l+1}$ ($0 \le a_i \lt 2^{17}$). It is guaranteed that $a$ can be generated using the steps performed by Gojou.
     42 
     43 It is guaranteed that the sum of $r - l + 1$ over all test cases does not exceed $2^{17}$.
     44 
     45 Output
     46 
     47 For each test case print an integer $x$. If there are multiple answers, print any.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 0 3
     57 
     58 3 2 1 0
     59 
     60 0 3
     61 
     62 4 7 6 5
     63 
     64 0 2
     65 
     66 1 2 3
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 0
     73 4
     74 3
     75 ```
     76 
     77 Note
     78 
     79 In the first test case, the original array is $[3, 2, 1, 0]$.
     80 
     81 In the second test case, the original array is $[0, 3, 2, 1]$.
     82 
     83 In the third test case, the original array is $[2, 1, 0]$.