QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#142626 | #6519. X Equals Y | BUET_POTATOES# | WA | 3ms | 3484kb | C++20 | 2.1kb | 2023-08-19 14:23:07 | 2023-08-19 14:23:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
vector<int> get(int x, int a){
vector<int> res;
while(x){
res.push_back(x % a);
x /= a;
}
return res;
}
void solve(){
int x, y, A, B;
cin>>x>>y>>A>>B;
if(x == 1 || y == 1){
if(x == y){
cout<<"YES\n";
cout<<"2 2\n";
}
else{
cout<<"NO\n";
}
return;
}
if(x <= A && y <= B){
cout<<"YES\n";
cout<<x<<" "<<y<<"\n";
return;
}
A = min(A, x-1);
B = min(B, y-1);
int loA = 2, loB = 2;
map<vector<int>, int> mp;
for(int a = 2; a*a <= x && a <= A; a++){
mp[get(x, a)] = a;
loA = a+1;
}
for(int b = 2; b*b <= y && b <= B; b++){
auto v = get(y,b);
if(mp.count(v) > 0){
int a = mp[v];
cout<<"YES\n";
cout<<a<< " " <<b<<"\n";
return;
}
loB = b+1;
}
/// p*a+q = x, p*b+q = y
for(int p = 1; p*p < min(x, y); p++){
if((x-y) % p != 0){
continue;
}
if(x < y){
int del = (y-x)/p;
/// b = a+del
int l = max(loA, loB-del);
int r = min(A, B-del);
l = max(l, x/(p+1)+1);
r = min(r, x/p);
if(l > r) continue;
cout<<"YES\n";
cout<<l<<" "<<l+del<<"\n";
}
else{
int del = (x-y)/p;
/// b+del = a
int l = max(loB, loA-del);
int r = min(B, A-del);
l = max(l, y/(p+1)+1);
r = min(r, y/p);
if(l > r) continue;
cout<<"YES\n";
cout<<l+del<<" "<<l<<"\n";
}
}
cout<<"NO\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int tc;
cin>>tc;
for(int cs = 1; cs <= tc; cs++){
solve();
}
return 0;
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3468kb
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: -100
Wrong Answer
time: 3ms
memory: 3484kb
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 590 331 YES 120 83 NO YES 14 148 YES 8 75 NO NO YES 244 246 YES 146 147 NO NO YES 77 66 YES 51 44 NO YES 25 10 NO YES 214 286 YES 143 179 YES 107 131 YES 86 104 YES 61 73 YES 48 57 YES 43 51 YES 33 39 YES 23 27 NO NO NO NO NO YES 406 136 YES 282 102 YES 217 82 YES 176 68 YES 148 58 YES 101 41 YE...
result:
wrong answer Integer parameter [name=a] equals to 120, violates the range [2, 31] (test case 2)