QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#139765 | #6519. X Equals Y | MaxBlazeResFire | WA | 2ms | 3752kb | C++14 | 1.9kb | 2023-08-14 15:31:56 | 2023-08-14 15:31:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int X,Y,A,B,swa;
inline bool solve2(){
vector<int> factor;
for( int p = 1 ; p * p < X ; p ++ )
if( ( X - Y ) % p == 0 ) factor.emplace_back( p );//cerr << p << "\n";
for( int p : factor ){
int L = max( X / ( p + 1 ) , ( X * p + X - Y ) / ( p * p + p ) ) + 1;
L = max( L , 2 + ( X - Y ) / p );
int R = min( min( A , X ) , min( B + ( X - Y ) / p , Y + ( X - Y ) / p ) );
R = min( R , X / p );
if( L <= R ){
int a = ( L + R ) >> 1,b = ( Y - X ) / p + a;
if( swa ) swap( a , b );
printf("YES\n%lld %lld\n",a,b);
return 1;
}
}
return 0;
}
vector< vector<int> > Fa,Fb;
inline bool solve3(){
int lenA = 0,lenB = 0;
Fa.clear(),Fb.clear();
Fa.emplace_back( vector<int>() ),Fb.emplace_back( vector<int>() );
for( int a = 2 ; a <= A && a * a <= X ; a ++ ){
Fa.emplace_back( vector<int>() ),lenA ++;
int tmp = X;
while( tmp ) Fa[lenA].emplace_back( tmp % a ),tmp /= a;
}
for( int b = 2 ; b <= B && b * b <= Y ; b ++ ){
Fb.emplace_back( vector<int>() ),lenB ++;
int tmp = Y;
while( tmp ) Fb[lenB].emplace_back( tmp % b ),tmp /= b;
}
int ptb = 1;
for( int pta = 1 ; pta <= lenA ; pta ++ ){
while( ptb <= lenB && Fb[ptb].size() > Fa[pta].size() ) ptb ++;
if( ptb > lenB ) return 0;
int LEN = Fa[pta].size(),flg = 0;
for( int j = 0 ; j < LEN ; j ++ )
if( Fa[pta][j] != Fb[ptb][j] ){ flg = 1; break; }
if( !flg ){
if( swa ) swap( pta , ptb );
printf("YES\n%lld %lld\n",pta + 1,ptb + 1);
return 1;
}
}
return 0;
}
inline void solve(){
scanf("%lld%lld%lld%lld",&X,&Y,&A,&B);
if( X == Y ){ printf("YES\n2 2\n"); return; }
if( X < Y ) swap( X , Y ),swap( A , B ),swa = 1; else swa = 0;
if( !solve2() ){ if( !solve3() ) printf("NO\n"); }
}
signed main(){
int testcase; scanf("%lld",&testcase);
while( testcase -- ) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3752kb
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 784 9483
result:
ok correct (6 test cases)
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 3708kb
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 673 414 YES 15 149 NO YES 266 268 NO YES 81 70 YES 253 48 YES 35 4 YES 277 349 NO NO NO NO YES 410 140 YES 101 78 YES 13 186 NO YES 103 5 YES 46 38 YES 11 248 NO NO YES 194 18 YES 141 110 NO YES 725 321 NO YES 56 185 NO YES 65 28 YES 57 11 YES 10 39 YES 91 51 YES 6 5 YES 57 10 NO NO NO NO YES 30...
result:
wrong answer wrong solution, (875 in base 35) != (100 in base 4) (test case 8)