QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#153506	#6519. X Equals Y	275307894a	WA	7ms	3864kb	C++14	1.9kb	2023-08-30 09:09:38	2023-08-30 09:09:39

Judging History

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

[2023-08-30 09:09:39]
评测

测评结果：WA
用时：7ms
内存：3864kb

查看

[2023-08-30 09:09:38]
提交

answer

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e5+5,M=N*40+5,K=600+5,mod=1e9+7,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
int x,y,A,B;
vector<pair<vector<int>,int> > a,b;
void print(int X,int Y){
	while(x||y){
		// assert(x%X==y%Y);
		x/=X;y/=Y;
	}
	printf("YES\n%d %d\n",X,Y);
}
void Solve(){
	int i,j;scanf("%d%d%d%d",&x,&y,&A,&B);
	if(x==y) {printf("YES\n2 2\n");return;}
	int X=sqrt(x)-eps,Y=sqrt(y)-eps;
	a.clear();b.clear();
	for(i=2;i<=A&&i<=X;i++) {
		vector<int> c;
		int z=x;for(j=0;z;j++) c.emplace_back(z%i),z/=i;
		a.emplace_back(c,i);
	}
	for(i=2;i<=B&&i<=Y;i++) {
		vector<int> c;
		int z=y;for(j=0;z;j++) c.emplace_back(z%i),z/=i;
		b.emplace_back(c,i);
	}
	sort(a.begin(),a.end());sort(b.begin(),b.end());
	while(!a.empty()&&!b.empty()){
		if(a.back().fi==b.back().fi){
			print(a.back().se,b.back().se);return;
		}
		if(a.back().fi<b.back().fi) b.pop_back();
		else a.pop_back();
	}
	X=max(X+1,2);Y=max(Y+1,2);
	while(X<=A&&Y<=B&&X<=x&&Y<=y){
		int l=min(A,x/(x/X)),r=min(B,y/(y/Y));
		if(x/X!=y/Y){
			if(x/X<y/Y) Y=r+1;else X=l+1;
			continue;
		}
		// cerr<<X<<' '<<Y<<'\n';
		int xl=x%X,xr=x%l,yl=y%Y,yr=y%r;
		if(xl%(x/X)==yl%(y/Y)&&max(xr,yr)<=min(xl,yl)) {
			int z=min(xl,yl);
			print(X+(xl-z)/(x/X),Y+(yl-z)/(y/Y));
			return;
		}
		X=l+1;Y=r+1;
	}
	puts("NO");
}
int main(){
	int t;
	scanf("%d",&t);
	// t=1;
	while(t--) Solve();
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3864kb

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: 3748kb

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
120 83
YES
8 75
NO
YES
146 147
NO
YES
51 44
YES
25 10
NO
YES
23 27
NO
NO
NO
NO
YES
52 22
YES
96 73
YES
12 185
NO
NO
YES
34 28
YES
10 247
NO
NO
YES
16 5
YES
132 101
NO
YES
220 119
NO
YES
20 63
NO
YES
65 28
NO
NO
YES
37 21
YES
6 5
NO
NO
NO
NO
NO
YES
43 17
NO
YES
36 34
YES
17 25
YES
95 14
NO
NO
NO
...

result:

wrong answer wrong solution, (9 in base 3) != (354 in base 118) (test case 114)