求助!WA pts45
查看原帖
求助!WA pts45
289056
北射天狼楼主2023/7/28 16:06
#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
	int s = 0,f = 1;char c = getchar();
	while (!isdigit(c)){if (c == '-')f = -1;c = getchar();}
	while (isdigit(c)){s = (s << 3) + (s << 1) + (c ^ 48);c = getchar();}
	return s*f;
}
int cnt,ans,a,b,c,x,y,z,tot;
int d1,d2,d3;
int tmp[5];
struct node{
    int a,b,c;
    int tot;
}A,B;
node calc(int x,int y,int z){
	tot = 0;
	while (1){
		int d1 = y - x;
		int d2 = z - y;
		if (d1 == d2)
		    break;
		if (d1 > d2){
			int d3 = (d1 - 1)/d2;
			y -= d3 * d2;
			z -= d3 * d2;
			tot += d3;
		}
		else {
			int d3 = (d2 - 1)/d1;
			tot += d3;
			x += d3 * d1;
			y += d3 * d1;
		}
	}
	return {x,y,z,tot};
}

bool check(int mid,int a,int b,int c,int x,int y,int z){
	tot = mid;
	while (tot){
	    int d1 = b - a,d2 = c - b;
		if (d1 == d2)
		   break;
		if (d1 > d2){
			int d3 = min((d1-1)/d2,tot);
			tot -= d3;
			b -= d3 * d2;
			c -= d3 * d2;
		}
		else {
			int d3 = min((d2-1)/d1,tot);
			tot -= d3;
			b += d3 * d1;
			a += d3 * d1;
		}
	}
	tot = mid;
	while (tot){
	    int d1 = y - x,d2 = z - y;
		if (d1 == d2)
		   break;
		if (d1 > d2){
			int d3 = min((d1-1)/d2,tot);
			tot -= d3;
			y -= d3 * d2;
			z -= d3 * d2;
		}
		else {
			int d3 = min((d2-1)/d1,tot);
			tot -= d3;
			y += d3 * d1;
			x += d3 * d1;
		}
	}
	return a == x && b == y && c == z;
}
signed main()
{
    for (int i=1;i<=3;i++)
        tmp[i] = read();
    sort(tmp+1,tmp+4);
    a = tmp[1],b = tmp[2],c = tmp[3];
    for (int i=1;i<=3;i++)
        tmp[i] = read();
    sort(tmp+1,tmp+4);
    x = tmp[1],y = tmp[2],z = tmp[3];
    A = calc(a,b,c);
    B = calc(x,y,z);
    if (!((A.a == B.a) && (A.b == B.b) && (A.c == B.c))){
    	puts("NO");
    	return 0;
	}
    if (A.tot < B.tot){
    	swap(A.a,B.a),swap(A.b,B.b),swap(A.c,B.c),swap(A.tot,B.tot);
    	swap(a,x);swap(b,y);swap(c,z);
	}
	ans = A.tot - B.tot;
	while (tot){
		//cout << tot;
		int d1 = b - a,d2 = c - b;
		if (d1 == d2)
		   break;
		if (d1 > d2){
			int d3 = min((d1-1)/d2,tot);
			tot -= d3;
			b -= d3 * d2;
			c -= d3 * d2;
		}
		else {
			int d3 = min((d2-1)/d1,tot);
			tot -= d3;
			a += d3 * d1;
			b += d3 * d1;
		}
	}
	int l = 0,r = B.tot;
	while (l <= r){
		int mid = l + r >> 1;
		if (check(mid,a,b,c,x,y,z)){
			r = mid-1;
			cnt = mid;
		} else l = mid+1;
	}
	puts("YES");
	printf("%lld\n",ans + cnt*2);
	return 0;
}

2023/7/28 16:06
加载中...