ZONeエナジー プログラミングコンテスト “HELLO SPACE” : F - 出会いと別れ

Eまでは順調だったのに、Fでやらかして残念。
https://atcoder.jp/contests/zone2021/tasks/zone2021_f

問題

Nが2の累乗である正整数であるとき、0～(N-1)のラベルを持つ頂点の全域木を作りたい。
ただし数列Aが与えられており、xとyのラベルの間に辺を張るとき、x xor yの値がAに含まれている場合は辺を張れない。
条件を満たす辺の張り方を構成せよ。

解法

Aに含まれない0～(N-1)の値をbit vectorとみなし、logN個のベクトルでN次元の空間を張れるかチェックしよう。
あとは0番の点だけの集合から初めて、各ベクトルvに対し、「集合内の全頂点に対し、そのラベルuからu^vのラベルの点に辺を張り、その頂点を加える」という作業を繰り返せばよい。

int N,M,L;
int A[1<<18];
int C[1<<18];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	while(1<<(L+1)<=N) L++;
	FOR(i,M) {
		cin>>x;
		B[x]=1;
	}
	vector<int> V;
	C[0]=1;
	FOR(i,N) {
		if(B[i]||C[i]) continue;
		FOR(j,N) if(C[j]) C[i^j]=1;
		V.push_back(i);
	}
	
	if(V.size()!=L) {
		cout<<-1<<endl;
		return;
	}
	
	vector<pair<int,int>> R;
	vector<int> hoge;
	hoge.push_back(0);
	FORR(v,V) {
		vector<int> hoge2;
		FORR(a,hoge) {
			R.push_back({a,a^v});
			hoge2.push_back(a);
			hoge2.push_back(a^v);
		}
		
		swap(hoge,hoge2);
	}
	
	FORR2(a,b,R) cout<<a<<" "<<b<<endl;
}

まとめ

最初掃きだして2WAしてしまった。