QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408450#6519. X Equals Yx17875487211WA 12ms4008kbC++142.7kb2024-05-10 12:31:292024-05-10 12:31:30

Judging History

你现在查看的是最新测评结果

  • [2024-05-10 12:31:30]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:4008kb
  • [2024-05-10 12:31:29]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,x,y,A,B,W[100],cntw;
bool flag,YES;
bool num_is_ok(int num,int lim){
	if(num>=2&&num<=lim) return 1;
	return 0;
}
bool check_w0(int a,int b,int w1){
	if(x-a*w1!=y-b*w1) return 0;
	int w0=x-a*w1;
	if(w1<0||w1>=min(a,b)) return 0;
	if(w0<0||w0>=min(a,b)) return 0;
	if(a*w1+w0==x&&b*w1+w0==y&&num_is_ok(a,A)&&num_is_ok(b,B)){
		if(flag) swap(a,b);
		printf("YES\n%lld %lld\n",a,b),YES=1;
		return 1;
	}
	return 0;
}
bool cal(int w1){
	int a=x/w1,b=y/w1;
	vector<int> proa,prob;
	for(int i=0;i<=10;i++)
		proa.push_back(a-i),proa.push_back(a+i),
		prob.push_back(b-i),prob.push_back(b+i);
	for(auto pa:proa)
		for(auto pb:prob)
			if(check_w0(pa,pb,w1)) return 1;
	return 0;
}
void DI(int Num,int bas){
	cntw=0;
	while(Num){
		W[++cntw]=Num%bas;
		Num/=bas;
	}
}
int num_base_onb(int di){
	int sum=0,mi=1;
	int tmp=y;
    for(int i=1;i<=cntw;i++){
		sum+=W[i]*mi;
        if(W[i]>=di) return -1;
		mi*=di;
        tmp/=di;
	}
    if(tmp) return -1;
	return sum;
}
int bin_seab(){
	int l=2,r=B;
	while(l<=r){
		int mid=(l+r)>>1;
		int NUM_BASE_ON=num_base_onb(mid);
		if(NUM_BASE_ON==y) return mid; 
		else if(NUM_BASE_ON<y) l=mid+1;
		else r=mid-1;
	} 
	return -1;
}
bool work_on_less_than_sqrta(int a){
	DI(x,a);
	int b=bin_seab();
	if(b!=-1){
		if(flag) swap(a,b);
		printf("YES\n%lld %lld\n",a,b),YES=1;
		return 1;
	}
	return 0;
}
int num_base_ona(int di){
	int sum=0,mi=1;
	int tmp=x;
    for(int i=1;i<=cntw;i++){
		sum+=W[i]*mi;
        if(W[i]>=di) return -1;
		mi*=di;
        tmp/=di;
	}
    if(tmp) return -1;
	return sum;
}
int bin_seaa(){
	int l=2,r=B;
	while(l<=r){
		int mid=(l+r)>>1;
		int NUM_BASE_ON=num_base_ona(mid);
		if(NUM_BASE_ON==x) return mid; 
		else if(NUM_BASE_ON<x) l=mid+1;
		else r=mid-1;
	} 
	return -1;
}
bool work_on_less_than_sqrtb(int b){
	DI(y,b);
	int a=bin_seaa();
	if(a!=-1){
		if(flag) swap(a,b);
		printf("YES\n%lld %lld\n",a,b),YES=1;
		return 1;
	}
	return 0;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		flag=0;
		scanf("%lld%lld%lld%lld",&x,&y,&A,&B);
		if(x<y) swap(x,y),swap(A,B),flag=1;
		YES=0;
		for(int i=1;i*i<=(x-y);i++)
			if((x-y)%i==0){
				if(cal((x-y)/i+1)) break;
				if(cal(i+1)) break;
				if(cal((x-y)/i)) break;
				if(cal(i)) break;
			}
		if(!YES)
			for(int a=2;a<=A&&a*a<=x;a++)
				if(work_on_less_than_sqrta(a)) break;
		if(!YES) 
			for(int b=2;b<=B&&b*b<=y;b++)
				if(work_on_less_than_sqrtb(b)) break;
		if(!YES&&x==y&&A>=x&&B>=y){
			if(x==1) printf("YES\n%lld %lld\n",x+1,x+1),YES=1;
			else if(num_is_ok(x,A)&&num_is_ok(y,B)) printf("YES\n%lld %lld\n",x,x),YES=1;
		}
		if(!YES) printf("NO\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3988kb

input:

6
1 1 1000 1000
1 2 1000 1000
3 11 1000 1000
157 291 5 6
157 291 3 6
10126 114514 789 12345

output:

YES
2 2
NO
YES
3 11
YES
4 5
NO
YES
6 10

result:

ok correct (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 12ms
memory: 4008kb

input:

1000
920 661 756 534
52 454 31 218
980 77 812 6
729 733 289 660
161 643 21 475
602 525 329 274
782 167 279 113
875 100 388 16
426 498 341 417
433 751 312 39
91 50 47 39
941 388 247 46
725 808 148 486
945 405 700 145
647 509 152 445
45 564 16 468
843 40 530 3
722 36 323 22
568 472 443 41
38 749 25 42...

output:

YES
131 94
YES
17 151
NO
YES
182 183
NO
YES
54 47
YES
260 55
NO
YES
213 249
NO
NO
NO
NO
YES
315 135
YES
107 84
YES
15 188
NO
NO
YES
35 29
YES
12 249
NO
NO
YES
196 20
YES
151 120
NO
YES
498 296
NO
YES
67 196
NO
YES
66 29
NO
NO
YES
94 54
YES
6 5
NO
NO
NO
NO
NO
YES
324 129
NO
YES
237 224
YES
211 411
YE...

result:

wrong answer you didn't find a solution but jury did (test case 54)