Big Secret (Codeforces 925C)
Tags: Math, constructive algorithms

Vitya has learned that the answer for The Ultimate Question of Life, the Universe, and Everything is not the integer 54 42, but an increasing integer sequence $$$a_1, \ldots, a_n$$$. In order to not reveal the secret earlier than needed, Vitya encrypted the answer and obtained the sequence $$$b_1, \ldots, b_n$$$ using the following rules:  $$$b_1 = a_1$$$; $$$b_i = a_i \oplus a_{i - 1}$$$ for all $$$i$$$ from 2 to $$$n$$$, where $$$x \oplus y$$$ is the bitwise XOR of $$$x$$$ and $$$y$$$. It is easy to see that the original sequence can be obtained using the rule $$$a_i = b_1 \oplus \ldots \oplus b_i$$$.However, some time later Vitya discovered that the integers $$$b_i$$$ in the cypher got shuffled, and it can happen that when decrypted using the rule mentioned above, it can produce a sequence that is not increasing. In order to save his reputation in the scientific community, Vasya decided to find some permutation of integers $$$b_i$$$ so that the sequence $$$a_i = b_1 \oplus \ldots \oplus b_i$$$ is strictly increasing. Help him find such a permutation or determine that it is impossible.

Input: The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$).The second line contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$ ($$$1 \leq b_i < 2^{60}$$$).

Output: If there are no valid permutations, print a single line containing "No".Otherwise in the first line print the word "Yes", and in the second line print integers $$$b'_1, \ldots, b'_n$$$ — a valid permutation of integers $$$b_i$$$. The unordered multisets $$$\{b_1, \ldots, b_n\}$$$ and $$$\{b'_1, \ldots, b'_n\}$$$ should be equal, i. e. for each integer $$$x$$$ the number of occurrences of $$$x$$$ in the first multiset should be equal to the number of occurrences of $$$x$$$ in the second multiset. Apart from this, the sequence $$$a_i = b'_1 \oplus \ldots \oplus b'_i$$$ should be strictly increasing.If there are multiple answers, print any of them.

Note: In the first example no permutation is valid.In the second example the given answer lead to the sequence $$$a_1 = 4$$$, $$$a_2 = 8$$$, $$$a_3 = 15$$$, $$$a_4 = 16$$$, $$$a_5 = 23$$$, $$$a_6 = 42$$$.

Sample Inputs:
3
1 2 3

6
4 7 7 12 31 61

Sample Outputs:
No

Yes
4 12 7 31 7 61

Solution (Python):
n = int(input())
s = [[] for i in range(60)]
for b in list(map(int, input().split())):
    for i in range(59, -1, -1):
        if b >> i & 1:
            s[i].append(b)
            break
ans = []
cur = 0
for i in range(n):
    fl = False
    for j in range(60):
        if s[j] != [] and cur >> j & 1 == 0:
            ans.append(s[j][-1])
            cur ^= s[j][-1]
            s[j].pop()
            fl = True
            break
    if not fl:
        print('No')
        exit()
print('Yes')
print(' '.join((str(i) for i in ans)))

Solution (Python):
n = int(input())
s = [[] for i in range(60)]
for b in list(map(int, input().split())):
    for i in range(59, -1, -1):
        if b >> i & 1:
            s[i].append(b)
            break
ans = []
cur = 0
for i in range(n):
    fl = False
    for j in range(60):
        if s[j] != [] and cur >> j & 1 == 0:
            ans.append(s[j][-1])
            cur ^= s[j][-1]
            s[j].pop()
            fl = True
            break
    if not fl:
        print('No')
        exit()
print('Yes')
print(' '.join((str(i) for i in ans)))

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
g = [[] for i in range(60)]
for x in a:
    for i in range(59, -1, -1):
        if x >> i & 1:
            g[i].append(x)
            break
ord = []
for i in range(59, -1, -1):
    nxt = []
    for x in ord:
        if x >> i & 1 and g[i]:
            nxt.append(g[i].pop())
        nxt.append(x)
    if g[i]:
        nxt.append(g[i].pop())
        if g[i]:
            print('No')
            exit()
    ord = nxt
print('Yes')
print(' '.join((str(i) for i in ord)))