codeforces-scrape

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

1742G.md (1640B)


      1 Source: https://codeforces.com/problemset/problem/1742/G
      2 
      3 G. Orray
      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 You are given an array $a$ consisting of $n$ nonnegative integers.
     22 
     23 Let's define the prefix OR array $b$ as the array $b_i = a_1~\mathsf{OR}~a_2~\mathsf{OR}~\dots~\mathsf{OR}~a_i$, where $\mathsf{OR}$ represents the [bitwise OR operation](https://en.wikipedia.org/wiki/Bitwise_operation#OR). In other words, the array $b$ is formed by computing the $\mathsf{OR}$ of every prefix of $a$.
     24 
     25 You are asked to rearrange the elements of the array $a$ in such a way that its prefix OR array is lexicographically maximum.
     26 
     27 An array $x$ is lexicographically greater than an array $y$ if in the first position where $x$ and $y$ differ, $x_i \gt y_i$.
     28 
     29 Input
     30 
     31 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.
     34 
     35 The second line of each test case contains $n$ nonnegative integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq 10^9$).
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case print $n$ integers — any rearrangement of the array $a$ that obtains the lexicographically maximum prefix OR array.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 4
     51 
     52 1 2 4 8
     53 
     54 7
     55 
     56 5 1 2 3 4 5 5
     57 
     58 2
     59 
     60 1 101
     61 
     62 6
     63 
     64 2 3 4 2 3 4
     65 
     66 8
     67 
     68 1 4 2 3 4 5 7 1
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 8 4 2 1 
     75 5 2 1 3 4 5 5 
     76 101 1 
     77 4 3 2 2 3 4 
     78 7 1 4 2 3 4 5 1
     79 ```