気持ちになっているので書きます。
解法
二進数で考えます。XOR(⊕)の性質を思い浮かべると、最上位bit(二進数の桁)で数を分類することを思いつきます。
そうしたとして、最も大きな桁を持つ数が二つ以上あれば、以下のように問いの条件(=累積XORが狭義単調増加)を満たせないことが直ちにわかります。
5(101)と7(111)があったとして、どのように並べても101⊕111=010(2)のため小さくなる
→最上位bitが打ち消しあって小さな数になる
では、二番目に大きな桁を持つ数はいくつあれば良いでしょうか?
上に書いたものと同じように考えて、同じ桁の数を二つ並べると、条件を満たせないことがわかります。
では、最も大きな桁を持つ数を挟むようにして並べるとどうなるでしょうか?これは二つの場合があります。例を示します。
5(101),7(111),8(1000)のとき
5,8,7と並べると不適
0101⊕1000=1101
1101⊕0111=1010
(7,8,5と並べても不適)5(101),7(111),12(1100)のとき
5,12,7と並べると適
0101⊕1100=1001
1001⊕0111=1110
三桁の数を並べるとき、それまでに並べた数の三桁目が1であれば、三桁目が上手く変化するため、それを挟むように二つ置くことができます。
逆に、三桁目が0である数を挟むように二つ並べると条件を満たしません。
これを一般化すると、次のことが言えそうです。
「n+1桁以上の数のみで作られた条件を満たす数列にn桁の数を挿入するときは、先頭から順にn桁目が1である数と交互になるように挿入しなければならない。」
こんな感じです。仮にすべての数のn桁目が1であるとすると
O O O O O O O に X を5個挿入する→X O X O X O X O X O O O
逆に、これを満たすように挿入できれば、挿入した数の前後について、n桁目が0→n桁目が1となり、n+1桁以上については仮定から条件を満たしていることがわかるので、挿入後の数列も条件を満たします。
実装
数列を読み込みつつ、桁数で分類します。
リストを作り、先頭にpushした後、whileで次のn桁目が立っている数まで飛んで、その後ろに数を挿入します。
この過程でリストの終端まで行ってしまった場合、Noを出力します。
#include<iostream> #include<cstdio> #include<vector> #include<list> #include<algorithm> using namespace std; int n; long long b; vector<long long>a[66]; list<long long>ans; main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%lld",&b); int cnt=0; while(b>>cnt)cnt++; a[cnt-1].push_back(b); } for(int i=60;i>=0;i--) { if(a[i].size()>0)ans.push_front(a[i][0]); list<long long>::iterator it=ans.begin(); for(int j=1;j<a[i].size();j++) { it++; while(it!=ans.end()&&!((*it>>i)&1))it++; if(it==ans.end()) { puts("No"); return 0; } it++; it=ans.insert(it,a[i][j]); } } puts("Yes"); int flag=0; for(long long it:ans) { if(flag++)putchar(' '); printf("%lld",it); } puts(""); }