A11654. Big Secret
编程题
普及/提高-
知识点
题目描述
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](https://en.wikipedia.org/wiki/Bitwise_operation#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.
- $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](https://en.wikipedia.org/wiki/Bitwise_operation#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.
输入格式
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}$ ).
The second line contains $n$ integers $b_1, \ldots, b_n$ ( $1 \leq b_i < 2^{60}$ ).
输出格式
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.
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.
输入输出样例
输入 #1
3 1 2 3
输出 #1
No
输入 #2
6 4 7 7 12 31 61
输出 #2
Yes 4 12 7 31 7 61
说明/提示
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$ .
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$ .