QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#153507 | #6519. X Equals Y | 275307894a | AC ✓ | 1116ms | 7372kb | C++14 | 1.9kb | 2023-08-30 09:16:19 | 2023-08-30 09:16:19 |
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),Y=sqrt(y);
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';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4052kb
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: 0
Accepted
time: 7ms
memory: 3960kb
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:
ok correct (1000 test cases)
Test #3:
score: 0
Accepted
time: 235ms
memory: 4144kb
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 4601 4534 YES 2665 3338 YES 1316 1324 NO YES 95178 89311 YES 467 521 YES 231155 178086 YES 9923 3142 YES 801 1245 YES 56397 91076 YES 149 350 YES 21813 21356 YES 483 960 YES 1106 587 YES 713 699 YES 1360 9003 NO YES 10582 4091 YES 12451 8292 YES 580 2359 YES 1144 1101 YES 1765 1712 YES 292 670 Y...
result:
ok correct (1000 test cases)
Test #4:
score: 0
Accepted
time: 750ms
memory: 7332kb
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 15697 55647 YES 54705 238708 YES 146889 31988 YES 14961767 18599668 YES 26084 32771 NO YES 4908 216251 YES 1773823 1745826 YES 2335 2446 NO YES 8104797 7759486 YES 52542 390541 YES 43464 45193 YES 66310 101363 YES 3084325 539148 YES 3152879 758952 NO YES 52717 115814 YES 696930 7...
result:
ok correct (1000 test cases)
Test #5:
score: 0
Accepted
time: 71ms
memory: 4252kb
input:
1000 11131470 5473008 893 586 160457243 377399003 195 363 33293118 10204988 348 650 76153236 165484206 788 591 363322142 108960566 994 862 10849 1346589 861 662 425071 7754389 221 245 5472186 246060285 479 804 699145 16995055 56 861 215170 3080970 423 722 355522 9691597 211 923 24159424 15965332 579...
output:
YES 36 30 YES 50 62 YES 50 37 NO NO YES 16 86 YES 28 74 YES 10 19 NO YES 33 83 YES 16 37 YES 93 81 YES 70 80 NO YES 50 56 YES 99 29 YES 47 33 YES 2 2 YES 14 77 YES 89 84 YES 42 7 YES 48 93 YES 48 22 YES 63 48 YES 73 96 NO YES 21 20 YES 36 55 YES 68 24 YES 11 89 YES 36 64 YES 13 34 YES 57 59 YES 65 6...
result:
ok correct (1000 test cases)
Test #6:
score: 0
Accepted
time: 1116ms
memory: 7372kb
input:
1000 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 994905890 324112256 607121052 999502221 99490...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok correct (1000 test cases)