Codeforces #931 : Div2 D1. XOR Break — Solo Version

一見部分点に見せかけて違う問題出すのやめてくれ…。
https://codeforces.com/contest/1934/problem/D1

問題

変数xの初期値はNである。
以下の処理を繰り返し、x=Mにできるか。
できるなら一例を示せ。

• 0＜y＜x かつ 0＜(x xor y)＜xとなるyを選び、x=yまたはx=(x xor y)とする

解法

処理を言い換えると、y xor z = xかつy,zがx未満となるようなy,zを選び、xをyまたはzにできることになる。
この上で、xを上のbitからMに合わせていこう。
あるbitが、xとMそれぞれ0か1かで分類していく。

int T;
ll N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		
		vector<ll> V={N};
		if((N^M)<N) {
			V.push_back(M);
		}
		else {
			if((N&M)!=M) {
				ll v=0;
				int cnt=0;
				for(i=60;i>=0;i--) {
					if(cnt==2) {
						v^=1LL<<i;
						continue;
					}
					if((N&(1LL<<i))==(M&(1LL<<i))) {
						v^=(N&(1LL<<i));
						continue;
					}
					if(M&(1LL<<i)) break;
					cnt++;
					if(cnt==1) v^=1LL<<i;
				}
				if(v!=N) V.push_back(v);
				N=v;
			}
			if((N^M)>=N) {
				cout<<-1<<endl;
				continue;
			}
			if(N!=M) V.push_back(M);
		}
		cout<<V.size()-1<<endl;
		FORR(v,V) cout<<v<<" ";
		cout<<endl;
	}
}

まとめ

処理回数の上限がかなりのヒントになっている。