AtCoder ABC #126 : F - XOR Matching

しょうもないミス。
https://atcoder.jp/contests/abc126/tasks/abc126_f

問題

整数M,Kが与えられる。
0～((2^M)-1)の整数を2個ずつ、計2^(M+1)要素からなる数列Aを考える。
A[L]=A[R]であるとき、xor(A[L...R])=Kとなるような数列を作成可能か。可能なら1例を示せ。

解法

K≧2^Mは当然解なし。
Mが1以外の場合、0～((2^M)-1)のxorを取ると0になる。
そこで、以下の数列を作ればよい。
(0～((2^M)-1)のうちK以外を昇順に並べる) K (0～((2^M)-1)のうちK以外を降順に並べる) K

確認してみると、以下の通りこれでうまくいく。

• A[L]・A[R]がK以外のとき、A[L...R]にはK以外の要素は2回ずつ現れるのでxorを取った値はK。
• A[L]・A[R]がKのとき、A[L...R]には0～((2^M)-1)にはKだけ2回、K以外1回現れるので、やはりxorはK。

M=1の場合だけは例外なのだが、解はテストケースにあるのでそれをまねしよう。

int N,K;


void solve() {
	int i,j,k,l,r,x,y; string s;
	vector<int> V;
	int num=0;
	cin>>N>>K;
	
	
	if(N==1&&K==1) {
		cout<<-1<<endl;
		return;
	}
	if(N==1&&K==0) {
		cout<<"0 0 1 1"<<endl;
		return;
	}
	if(K>=1<<N) {
		cout<<-1<<endl;
		return;
	}
	
	FOR(i,1<<N) if(i!=K) cout<<i<<" ";
	cout<<K<<" ";
	for(i=(1<<N)-1;i>=0;i--) if(i!=K) cout<<i<<" ";
	cout<<K;
	cout<<endl;
	
}

まとめ

サンプルにあるM=1見落としでWAしてしまった。