QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #153505 | #6519. X Equals Y | 275307894a | WA | 7ms | 3944kb | C++14 | 1.9kb | 2023-08-30 09:08:27 | 2023-08-30 09:08:28 |
Judging History
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';
}
Details
Tip: Click on the bar to expand more detailed information
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)