codeforces-scrape

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

1991B.md (1944B)


      1 Source: https://codeforces.com/problemset/problem/1991/B
      2 
      3 B. AND Reconstruction
      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 an array $b$ of $n - 1$ integers.
     22 
     23 An array $a$ of $n$ integers is called good if $b_i = a_i \, \& \, a_{i + 1}$ for $1 \le i \le n-1$, where $\&$ denotes the [bitwise AND operator](https://en.wikipedia.org/wiki/Bitwise_operation#AND).
     24 
     25 Construct a good array, or report that no good arrays exist.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the length of the array $a$.
     32 
     33 The second line of each test case contains $n - 1$ integers $b_1, b_2, \ldots, b_{n - 1}$ ($0 \le b_i \lt 2^{30}$) — the elements of the array $b$.
     34 
     35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     36 
     37 Output
     38 
     39 For each test case, output a single integer $-1$ if no good arrays exist.
     40 
     41 Otherwise, output $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \lt 2^{30}$) — the elements of a good array $a$.
     42 
     43 If there are multiple solutions, you may output any of them.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 2
     53 
     54 1
     55 
     56 3
     57 
     58 2 0
     59 
     60 4
     61 
     62 1 2 3
     63 
     64 5
     65 
     66 3 5 4 2
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 5 3
     73 3 2 1
     74 -1
     75 3 7 5 6 3
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, $b = [1]$. A possible good array is $a=[5, 3]$, because $a_1 \, \& \, a_2 = 5 \, \& \, 3 = 1 = b_1$.
     81 
     82 In the second test case, $b = [2, 0]$. A possible good array is $a=[3, 2, 1]$, because $a_1 \, \& \, a_2 = 3 \, \& \, 2 = 2 = b_1$ and $a_2 \, \& \, a_3 = 2 \, \& \, 1 = 0 = b_2$.
     83 
     84 In the third test case, $b = [1, 2, 3]$. It can be shown that no good arrays exist, so the output is $-1$.
     85 
     86 In the fourth test case, $b = [3, 5, 4, 2]$. A possible good array is $a=[3, 7, 5, 6, 3]$.