WA35求调
  • 板块P1852 跳跳棋
  • 楼主CBQZZYJ
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/25 16:35
  • 上次更新2024/11/25 19:42:58
查看原帖
WA35求调
977730
CBQZZYJ楼主2024/11/25 16:35
#include<bits/stdc++.h>
using namespace std;
inline pair<int,pair<int,pair<int,int>>> getDep(pair<int,pair<int,int>> val){
	int ret=0,x=val.first,y=val.second.first,z=val.second.second;
	while(y-x!=z-y){
		int dx=y-x,dy=z-y;
		if(dx<dy){
			ret+=(dy-1)/dx;int dz=dy-(dy-1)/dx*dx;y=z-dz;x=y-dx;
		}else{
			ret+=(dx-1)/dy;int dz=dx-(dx-1)/dy*dy;y=x+dz;z=y+dy;
		}
	}
	return {ret,{x,{y,z}}};
}
inline pair<int,pair<int,int>> List(pair<int,pair<int,int>> val,int ret){
	int x=val.first,y=val.second.first,z=val.second.second;//cout<<x<<' '<<y<<' '<<z<<endl;
	while(ret&&y-x!=z-y){
		int dx=y-x,dy=z-y;
		if(dx<dy){
			if((dy-1)/dx<ret){
				ret-=(dy-1)/dx;int dz=dy-(dy-1)/dx*dx;y=z-dz;x=y-dx;			
			}else{
				int dz=z-y;dz-=ret*dx;y=z-dz;x=y-dx;ret=0;
			}
		}else{
			if((dx-1)/dy<ret){
				ret-=(dx-1)/dy;int dz=dx-(dx-1)/dy*dy;y=x+dz;z=y+dy;			
			}else{
				int dz=y-x;dz-=ret*dy;y=x+dz;z=y+dy;ret=0;
			}
		}	
	}return {x,{y,z}};
}
inline pair<int,pair<int,int>> AskLca(pair<int,pair<int,int>> L,pair<int,pair<int,int>> R){
	if(L==R){
		return R;
	}
	for(int i=0;i<31;i++){
		pair<int,pair<int,int>> l=List(L,(1<<i)),r=List(R,(1<<i));
		if(l!=r){
			L=l,R=r;
		}
	}return List(L,1);
}
int a,b,c,x,y,z;
signed main(){
	priority_queue<int,vector<int>,greater<int>> Q;
	int v;cin>>v;Q.push(v);cin>>v;Q.push(v);cin>>v;Q.push(v);a=Q.top();Q.pop();b=Q.top();Q.pop();c=Q.top();Q.pop();cin>>v;Q.push(v);cin>>v;Q.push(v);cin>>v;Q.push(v);x=Q.top();Q.pop();y=Q.top();Q.pop();z=Q.top();Q.pop();
	pair<int,pair<int,pair<int,int>>> d1=getDep({a,{b,c}}),d2=getDep({x,{y,z}});
	if(d1.second!=d2.second){
		cout<<"NO"<<endl;return 0;
	}cout<<"YES"<<endl;
	pair<int,pair<int,int>> L=List({a,{b,c}},d1.first-min(d1.first,d2.first)),R=List({x,{y,z}},d2.first-min(d1.first,d2.first));
	pair<int,pair<int,int>> p=AskLca(L,R);
	cout<<d1.first+d2.first-2*getDep(p).first;
}
2024/11/25 16:35
加载中...