TypeDB Forces 2023 : E. The Harmonization of XOR

悪くはなかった回。
https://codeforces.com/contest/1787/problem/E

問題

整数N,K,Xが与えられる。
1～Nの各値を、K個の集合に分ける。
その際、各集合において要素のbitwise-orがXとなるようにできるか。
できるなら一例を示せ。

解法

まず、単独でXになるもの及び2要素でXになるものを組み合わせ、最大K組作れるか判定しよう。
残りの要素のxorが0になっていればよく、その場合それらの要素を適当に1つの組に追加しよう。

int T;
int N,K,X;
vector<int> R[252525];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K>>X;
		FOR(i,K) R[i].clear();
		set<int> S;
		for(i=1;i<=N;i++) S.insert(i);
		int num=0;
		for(i=N;i>=1;i--) if(num<K) {
			if(i==X) {
				R[num++]={i};
				S.erase(i);
			}
			else if(S.count(i)&&S.count(i^X)) {
				R[num++]={i,i^X};
				S.erase(i);
				S.erase(i^X);
			}
		}
		x=X;
		FORR(a,S) {
			R[0].push_back(a);
			x^=a;
		}
		if(num<K||x!=X) {
			cout<<"NO"<<endl;
			continue;
		}
		
		cout<<"YES"<<endl;
		FOR(i,K) {
			cout<<R[i].size();
			sort(ALL(R[i]));
			FORR(r,R[i]) cout<<" "<<r;
			cout<<endl;
		}
	}
}

まとめ

割と雑にやったけど合ってたみたいね。