求助!80分wa
  • 板块P1852 跳跳棋
  • 楼主RiceFruit
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/26 18:25
  • 上次更新2023/10/27 18:17:26
查看原帖
求助!80分wa
541916
RiceFruit楼主2022/7/26 18:25

这是代码:

#include <bits/stdc++.h>
using namespace std;
void sleep(int p);int read();int read(int p);
#define ll long long
#define ull unsigned long long
#define db double
const int N=1000001,inf=0x3f3f3f3f,mod=1e9+7;
struct sa{
	int a;
	int b;
	int c;
	void st(){
		if(a>b)swap(a,b);
		if(a>c)swap(a,c);
		if(b>c)swap(b,c);
	}
	int len;
}; 
bool check(sa a,sa b){
	a.st(),b.st();
	return !(a.a!=b.a||a.b!=b.b||a.c!=b.c);
}
bool cmp(sa a,sa b){
	a.st(),b.st();
	return a.a==b.a?(a.b==b.b?(a.c<b.c):a.b<b.b):a.a<b.a;
}
sa getfa(sa now){
	now.len=0;
	while(now.b-now.a!=now.c-now.b){
		int d1=now.b-now.a,d2=now.c-now.b;
		if(d1<d2){
			int x=d2/d1-(d2%d1==0);
			now.a+=x*d1;
			now.b+=x*d1;
			now.len+=x;
		}
		else{
			int x=d1/d2-(d1%d2==0);
			now.c-=x*d2;
			now.b-=x*d2;
			now.len+=x;
		}
		now.st();
	} 
	return now;
}
sa jump(sa now,int up){
	while(up){
		int d1=now.b-now.a,d2=now.c-now.b;
		if(d1==d2){
			return now;
		}
		if(d1<d2){
			int x=min(d2/d1-(d2%d1==0),up);
			now.a+=x*d1;
			now.b+=x*d1;
			up-=x;
		}
		else{
			int x=min(d1/d2-(d1%d2==0),up);
			now.c-=x*d2;
			now.b-=x*d2;
			up-=x;
		}
		now.st();
	}
	return now;
}
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	sa now,to;
	scanf("%d%d%d%d%d%d",&now.a,&now.b,&now.c,&to.a,&to.b,&to.c);
	sa fnow=getfa(now),fto=getfa(to);
	if(!check(fnow,fto)){
		cout<<"NO";
		return 0;
	}
	if(fto.len>fnow.len){
		swap(now,to);
		swap(fnow,fto);
	}
	now=jump(now,fnow.len-fto.len);
	int l=0,r=100000000,lca;
	while(l<r){
		int mid=l+r>>1;
		if(check(jump(now,mid),jump(to,mid)))r=mid,lca=mid;
		else l=mid+1;
	}
	cout<<"YES\n"<<fnow.len-fto.len+lca*2;
	return 0;
}
void sleep(int p){for(ll i=1;i<=p*100000;i++)int x;return;}
inline int read(){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline int read(long long p){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();x=x%p;}return x*f;}
2022/7/26 18:25
加载中...