QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#358210 | #6519. X Equals Y | Doqe | WA | 49ms | 8016kb | C++20 | 1.8kb | 2024-03-19 18:11:32 | 2024-03-19 18:11:32 |
Judging History
answer
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(1375413);
unsigned msk[32];
unsigned F(int x,int y)
{
unsigned C=0,A=0;
while(x)A+=msk[C++]*(x%y),x/=y;
return A;
}
string tr(int x,int y)
{
string A;
while(x)A+=to_string(x%y),x/=y;
return A;
}
struct node
{
int l,r,v;
}K[101000];
int t;int X,Y;
void YES(int x,int y)
{
cout<<"YES\n"<<x<<" "<<y<<"\n";
// cerr<<tr(X,x)<<" "<<tr(Y,y)<<endl;
}
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int rd() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
void solve()
{
gp_hash_table<unsigned,int>S;
int x=rd(),y=rd(),A=rd(),B=rd();
X=x,Y=y;
if(x==1||y==1)
{
if(x==y)return YES(2,2);
if(x!=y){cout<<"NO\n";return;}
}
if(A>=x&&B>=y)return YES(x,y);
A=min(A,x),B=min(B,y);
int lA=min(A,(int)sqrt(x)),lB=min(B,(int)sqrt(y));
S.clear();
for(int i=2;i<=lA&&i<=500;++i)S[F(x,i)]=i;unsigned w1;
for(int i=2;i<=lB&&i<=500;++i)if(S.find(w1=F(y,i))!=S.end())return YES(S[w1],i);
t=0;
for(int l=lA+1,r,w;l<=A;l=r+1)
{
r=x/(w=x/l);
K[++t]={l,min(A,r),w};
}
int p=1;
for(int l=lB+1,r,w;l<=B;l=r+1)
{
r=y/(w=y/l);r=min(B,r);
while(p<=t&&K[p].v>w)++p;
if(p<=t&&K[p].v==w)
{
if(x%w!=y%w)continue;
int xl=x-K[p].r*w,xr=x-K[p].l*w;
int yl=y- r*w,yr=y- l*w;
if(max(xl,yl)<=min(xr,yr))
{
int z=max(xl,yl);
YES((x-z)/w,(y-z)/w);
return;
}
}
}
cout<<"NO\n";
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
for(int i=0;i<31;++i)msk[i]=rnd();
int T=rd();
while(T--)solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7692kb
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: 0
Accepted
time: 2ms
memory: 7820kb
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 8 75 NO YES 182 183 NO YES 54 47 YES 25 10 NO YES 23 27 NO NO NO NO YES 52 22 YES 107 84 YES 15 188 NO NO YES 35 29 YES 12 249 NO NO YES 16 5 YES 151 120 NO YES 249 148 NO YES 22 65 NO YES 66 29 NO NO YES 37 21 YES 6 5 NO NO NO NO NO YES 43 17 NO YES 38 36 YES 17 25 YES 96 15 NO NO NO...
result:
ok correct (1000 test cases)
Test #3:
score: 0
Accepted
time: 36ms
memory: 5748kb
input:
1000 312788 308299 292039 230765 263760 329714 198045 86472 945524 951268 792172 748100 922790 262573 363596 34883 755556 714487 234743 610394 413603 489527 114329 351936 409240 356171 378350 234973 300813 97383 263307 49846 579258 900270 84403 704902 563965 876076 387516 770189 36896 156893 23161 1...
output:
YES 4668 4601 YES 2691 3364 YES 1316 1324 NO YES 107936 102069 YES 806 954 YES 288042 234973 YES 10027 3246 YES 801 1245 YES 62662 97341 YES 139 338 YES 27151 26694 YES 483 960 YES 1106 587 YES 894 865 YES 1381 9024 NO YES 10657 4166 YES 12558 8399 YES 581 2360 YES 1145 1102 YES 1768 1715 YES 68 138...
result:
ok correct (1000 test cases)
Test #4:
score: -100
Wrong Answer
time: 49ms
memory: 8016kb
input:
1000 981241785 906230829 601363803 626653490 197057696 698550046 128696358 449956015 182548925 796382933 101642956 339324198 816288818 177783961 308532802 32376477 628394197 777548138 355072973 757299936 599075146 752655475 473746059 323396924 261214299 95047810 181049121 60329182 7484303 329571035 ...
output:
YES 35005 32329 YES 15698 55648 YES 54720 238723 YES 146893 31992 YES 15326687 18964588 YES 26084 32771 NO YES 4910 216253 YES 1796495 1768498 YES 29675 32561 NO YES 8181622 7836311 YES 52569 390568 YES 43467 45196 YES 66325 101378 YES 3087161 541984 YES 3156893 762966 NO YES 52726 115823 YES 696995...
result:
wrong answer you didn't find a solution but jury did (test case 762)