QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#153505#6519. X Equals Y275307894aWA 7ms3944kbC++141.9kb2023-08-30 09:08:272023-08-30 09:08:28

Judging History

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

  • [2023-08-30 09:08:28]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:3944kb
  • [2023-08-30 09:08:27]
  • 提交

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';
}

詳細信息

Test #1:

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

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

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
36 26
YES
8 75
NO
YES
28 28
YES
13 53
YES
27 23
YES
25 10
YES
87 10
YES
21 24
YES
21 37
YES
15 8
YES
49 20
YES
27 31
YES
49 21
YES
29 23
YES
7 94
NO
YES
120 6
YES
27 22
YES
7 149
NO
YES
14 17
YES
16 5
YES
31 25
YES
15 28
YES
43 25
YES
13 82
YES
12 35
YES
81 12
YES
45 20
YES
62 12
YES
11 41
YES
3...

result:

wrong answer wrong solution, (920 in base 36) != (661 in base 26) (test case 1)