CF925C.Big Secret

提高+/省选-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

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 a1,…,ana_1, \ldots, a_n. In order to not reveal the secret earlier than needed, Vitya encrypted the answer and obtained the sequence b1,…,bnb_1, \ldots, b_n using the following rules:

  • b1=a1b_1 = a_1;
  • bi=ai⊕ai−1b_i = a_i \oplus a_{i - 1} for all ii from 2 to nn, where x⊕yx \oplus y is the bitwise XOR of xx and yy.

It is easy to see that the original sequence can be obtained using the rule ai=b1⊕…⊕bia_i = b_1 \oplus \ldots \oplus b_i.

However, some time later Vitya discovered that the integers bib_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 bib_i so that the sequence ai=b1⊕…⊕bia_i = b_1 \oplus \ldots \oplus b_i is strictly increasing. Help him find such a permutation or determine that it is impossible.

维佳得知,“生命、宇宙以及一切的终极问题”的答案并非整数 54 42,而是一个严格递增的整数序列 a1,…,ana_1, \ldots, a_n。为了不提前泄露这一秘密,维佳对答案进行了加密,得到序列 b1,…,bnb_1, \ldots, b_n,加密规则如下:

  • b1=a1b_1 = a_1;
  • 对所有 ii 从 2 到 nn,有 bi=ai⊕ai−1b_i = a_i \oplus a_{i - 1},其中 x⊕yx \oplus y 表示 xx 与 yy 的按位异或运算。

容易验证,原始序列可通过规则 ai=b1⊕…⊕bia_i = b_1 \oplus \ldots \oplus b_i 还原。

然而,过了一段时间,维佳发现密文中的整数 bib_i 被打乱了顺序,此时若直接按上述规则解密,所得序列可能不再递增。为维护自己在科学界中的声誉,瓦夏决定找出 bib_i 的某个排列,使得由 ai=b1⊕…⊕bia_i = b_1 \oplus \ldots \oplus b_i 所生成的序列严格递增。请帮助他找到这样的一个排列,或判定其不存在。

输入格式

The first line contains a single integer nn (1≤n≤1051 \leq n \leq 10^5).

The second line contains nn integers b1,…,bnb_1, \ldots, b_n (1≤bi<2601 \leq b_i \lt 2^{60}).

第一行包含一个整数 nn(1≤n≤1051 \leq n \leq 10^5)。

第二行包含 nn 个整数 b1,…,bnb_1, \ldots, b_n(1≤bi<2601 \leq b_i \lt 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 b1′,…,bn′b'_1, \ldots, b'_n — a valid permutation of integers bib_i. The unordered multisets b1,…,bn{b_1, \ldots, b_n} and b1′,…,bn′{b'_1, \ldots, b'_n} should be equal, i. e. for each integer xx the number of occurrences of xx in the first multiset should be equal to the number of occurrences of xx in the second multiset. Apart from this, the sequence ai=b1′⊕…⊕bi′a_i = b'_1 \oplus \ldots \oplus b'_i should be strictly increasing.

If there are multiple answers, print any of them.

如果不存在合法的排列,则输出一行“No”。

否则,第一行输出“Yes”,第二行输出整数 b1′,…,bn′b'_1, \ldots, b'_n —— 即整数 bib_i 的一个合法排列。多重集 {b1,…,bn}\{b_1, \ldots, b_n\} 与 {b1′,…,bn′}\{b'_1, \ldots, b'_n\} 应当无序相等,即对每个整数 xx,其在第一个多重集中出现的次数应等于其在第二个多重集中出现的次数。此外,序列 ai=b1′⊕…⊕bi′a_i = b'_1 \oplus \ldots \oplus b'_i 必须严格递增。

若存在多个答案,输出任意一个即可。

输入输出样例

  • 输入#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 a1=4a_1 = 4, a2=8a_2 = 8, a3=15a_3 = 15, a4=16a_4 = 16, a5=23a_5 = 23, a6=42a_6 = 42.

在第一个例子中,不存在有效的排列。

在第二个例子中,给定的答案生成了序列 a1=4a_1 = 4,a2=8a_2 = 8,a3=15a_3 = 15,a4=16a_4 = 16,a5=23a_5 = 23,a6=42a_6 = 42。

输入解题思路,AI测评打分。不知道怎么写?

首页