# 【题目】Orray

Codeforces Round #827 (Div. 4)

G. Orray

https://codeforces.com/contest/1742/problem/G

2 seconds / 256 megabytes

standard input / standard output

### Problem

You are given an array $a$ consisting of $n$ nonnegative integers.

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. In other words, the array $b$ is formed by computing the $\mathsf{OR}$ of every prefix of $a$.

You are asked to rearrange the elements of the array $a$ in such a way that its prefix OR array is lexicographically maximum.

An array $x$ is lexicographically greater than an array $y$ if in the first position where $x$ and $y$ differ, $x_i > y_i$.

### Input

The first line of the input contains a single integer $1 \le t \le 100$ — the number of test cases. The description of test cases follows.

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$.

The second line of each test case contains $n$ nonnegative integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

### Output

For each test case print $n$ integers — any rearrangement of the array $a$ that obtains the lexicographically maximum prefix OR array.

input:

5
4
1 2 4 8
7
5 1 2 3 4 5 5
2
1 101
6
2 3 4 2 3 4
8
1 4 2 3 4 5 7 1

output:

8 4 2 1
5 2 1 3 4 5 5
101 1
4 3 2 2 3 4
7 1 4 2 3 4 5 1

### 题解

int pre = 0, tmp = 0;
for (int i = 0; i < n; i++)
{
int idx = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && tmp < (pre | a[j]))
{
tmp = (pre | a[j]);
idx = j;
}
}
pre = tmp;
cout << a[idx] << ' ';
vis[idx] = true;
}

### 代码

#include <bits/stdc++.h>

using namespace std;

void solve()
{
int n;
cin >> n;
vector<int> a(n);
vector<bool> vis(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int pre = 0, tmp = 0;
for (int i = 0; i < n; i++)
{
int idx = -1;
for (int j = 0; j < n; j++)
{
if (!vis[j] && tmp < (pre | a[j]))
{
tmp = (pre | a[j]);
idx = j;
}
}
if (idx == -1)
break;
pre = tmp;
cout << a[idx] << ' ';
vis[idx] = true;
}
for (int i = 0; i < n; i++)
if (!vis[i])
cout << a[i] << ' ';
cout << endl;
}

int main()
{
int t;
cin >> t;
while (t--)
solve();
return 0;
}