QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#167034#6519. X Equals Yucup-team134#WA 7ms3764kbC++141.5kb2023-09-06 23:41:492023-09-06 23:41:49

Judging History

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

  • [2023-09-06 23:41:49]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3764kb
  • [2023-09-06 23:41:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

vector<pair<vector<int>,int>> Cand(int x,int A,int SQ){
	vector<pair<vector<int>,int>> ans;
	for(int mod=2;mod<=min(SQ,A);mod++){
		vector<int> tmp;
		int Z=x;
		while(Z>0){
			tmp.pb(Z%mod);
			Z/=mod;
		}
		ans.pb({tmp,mod});
	}
	sort(ans.begin(),ans.end());
	return ans;
}

bool Solve(int x,int y,int A,int B,int&M1,int&M2){
	if(x==y){
		M1=2;
		M2=2;
		return true;
	}

	int SQ=sqrt(x)+3;
	vector<pair<vector<int>,int>> candA=Cand(x,A,SQ);
	vector<pair<vector<int>,int>> candB=Cand(y,B,SQ);
	for(int i=0,j=0;i<candA.size();i++){
		while(j<candB.size() && candB[j].first<candA[i].first){
			j++;
		}
		if(j<candB.size() && candA[i].first==candB[j].first){
			M1=candA[i].second;
			M2=candB[j].second;
			return true;
		}
	}

	for(int a1=1;a1<=SQ;a1++){
		int L1=x/(a1+1)+1;
		int R1=x/a1;

		L1=max(L1,2);
		R1=min(R1,A);

		int L2=y/(a1+1)+1;
		int R2=y/a1;

		L2=max(L2,2);
		R2=min(R2,B);

		int diff=y-x;
		if(diff%a1==0){
			int gap=diff/a1;
			int L3=max(L2,L1+gap);
			int R3=min(R2,R1+gap);
			if(L3<=R3){
				M1=L3-gap;
				M2=L3;
				return true;
			}
		}
	}

	return false;
}

int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int x,y,A,B;
		scanf("%i %i %i %i",&x,&y,&A,&B);
		int M1,M2;
		bool ok;
		if(x<=y){
			ok=Solve(x,y,A,B,M1,M2);
		}else{
			ok=Solve(y,x,B,A,M2,M1);
		}
		if(ok){
			printf("YES\n");
			printf("%i %i\n",M1,M2);
		}else{
			printf("NO\n");
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
2 10
YES
4 5
NO
YES
6 10

result:

ok correct (6 test cases)

Test #2:

score: -100
Wrong Answer
time: 7ms
memory: 3728kb

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
590 331
YES
14 148
NO
YES
244 246
NO
YES
77 66
YES
247 42
NO
YES
214 286
NO
NO
NO
NO
YES
406 136
YES
96 73
YES
12 185
NO
YES
103 5
YES
45 37
YES
10 247
NO
NO
YES
193 17
YES
132 101
NO
YES
701 297
NO
YES
45 174
NO
YES
65 28
YES
57 11
YES
10 39
YES
89 49
YES
6 5
YES
57 10
NO
NO
NO
NO
YES
282 87
NO...

result:

wrong answer wrong solution, (722 in base 103) != (36 in base 5) (test case 18)