45pts 其余MLE,悬关求调
查看原帖
45pts 其余MLE,悬关求调
325086
little_magicstar楼主2023/8/9 18:43
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
	int x, y, z;
}a1, a2;
void paixu(){
	if(a1.x > a1.y)
		swap(a1.x, a1.y);
	if(a1.y > a1.z)
		swap(a1.y, a1.z);
	if(a1.x > a1.y)
		swap(a1.x, a1.y);
	if(a2.x > a2.y)
		swap(a2.x, a2.y);
	if(a2.y > a2.z)
		swap(a2.y, a2.z);
	if(a2.x > a2.y)
		swap(a2.x, a2.y);
}
bool operator == (node xx, node yy){
	return xx.x == yy.x && xx.y == yy.y && xx.z == yy.z;
}
bool operator != (node xx, node yy){
	return !(xx == yy);
}
int d1, d2, k;
inline int dep(node a, int tcnt, node &now){
	d1 = a.y - a.x;
	d2 = a.z - a.y;
	if(d1 == d2){
		now = a;
		return tcnt;
	}
	if(d1 < d2){
		k = (d2 - 1) / d1;
		a.x += k * d1;
		a.y += k * d1;
		return dep(a, tcnt + k, now);
	}
	k = (d1 - 1) / d2;
	a.y -= k * d2;
	a.z -= k * d2;
	return dep(a, tcnt + k, now);
}
inline node jump(node a, int len){
	if(len == 0)
		return a;
	d1 = a.y - a.x;
	d2 = a.z - a.y;
	if(d1 < d2){
		k = (d2 - 1) / d1;
		if(k > len)
			k = len;
		a.x += k * d1;
		a.y += k * d1;
		return jump(a, len - k);
	}
	k = (d1 - 1) / d2;
	if(k > len)
		k = len;
	a.y -= k * d2;
	a.z -= k * d2;
	return jump(a, len - k);
}
long long ans;
int dep1, dep2, mid;
int main(){
	scanf("%d%d%d%d%d%d", &a1.x, &a1.y, &a1.z, &a2.x, &a2.y, &a2.z);
	paixu();
	node r1, r2;
	dep1 = dep(a1, 1, r1);
	dep2 = dep(a2, 1, r2);
	if(r1 != r2){
		puts("NO");
		return 0;
	}
	if(dep1 < dep2){
		swap(dep1, dep2);
		swap(a1, a2);
	}
	ans += dep1 - dep2;
	a1 = jump(a1, dep1 - dep2);
	if(a1 == a2){
		puts("YES");
		printf("%d\n", ans);
		return 0;
	}
	int l = 1, r = dep1;
	while(l < r){
		mid = (l + r) >> 1;
		if(jump(a1, mid) == jump(a2, mid))
			r = mid;
		else
			l = mid + 1;
	}
	ans += 2 * l;
	printf("YES\n%d\n", ans);
	return 0;
}
2023/8/9 18:43
加载中...