文件详细信息

下载本文件

本文件的大小为 1096 字节。

#include<algorithm>
#include<cstdio>
#include<unordered_map>
typedef long long ll;
ll n,S,X;
std::unordered_map<ll,std::pair<ll,ll>>dp,nxt;
inline void upd(const ll x,const std::pair<ll,ll>&y){
	if(nxt.count(x))nxt[x]=std::min(nxt[x],y);
	else nxt[x]=y;
}
void solve(){
	scanf("%lld%lld%lld",&n,&S,&X);
	dp[0]={0,n};
	for(int i=60;i>=0;i--){
		const ll f=(X>>i)&1;
		ll a,b,cur,d;
		for(const std::pair<ll,std::pair<ll,ll>>&it:dp){
			a=it.second.first,b=it.second.second,cur=it.first*2+((S>>i)&1);
			if(cur>=(n<<1)||cur<f)continue;
			if(n-b>=f){
				d=((std::min(cur,n-b)-f)&-2ll)+f;
				upd(cur-d,{a,b});
				if(cur==d&&d>1)upd(2,{a,b});
			}
			d=((std::min(cur,n)-f)&-2ll)+f;
			if(b+d>n)upd(cur-d,{a|(1ll<<i),b+d-n});
			if(cur==d||b+d-n==n){
				d-=2;
				if(b+d>n)upd(cur-d,{a|(1ll<<i),b+d-n});
			}
		}
		dp.swap(nxt),nxt.clear();
	}
	if(dp.count(0))printf("%lld\n",dp[0].first);
	else puts("-1");
	dp.clear();
}
int main(){
	freopen("xs.in","r",stdin);
	freopen("xs.out","w",stdout);
	int T;
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}