QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116659 | #6519. X Equals Y | ITMO_pengzoo# | WA | 252ms | 3568kb | C++20 | 2.6kb | 2023-06-29 18:32:13 | 2023-06-29 18:32:16 |
Judging History
answer
// Nikita Golikov, 2023
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#ifdef GOLIKOV
#include "/Users/golikovnik/contests/debug.h"
#else
#define debug(...) ;
#endif
template <class A, class B>
bool smin(A& x, B&& y) {
if (y < x) {
x = y;
return true;
}
return false;
}
template <class A, class B>
bool smax(A& x, B&& y) {
if (x < y) {
x = y;
return true;
}
return false;
}
void solveTest() {
int x, y, A, B;
cin >> x >> y >> A >> B;
if (x == y) {
cout << "YES\n" << 2 << ' ' << 2 << '\n';
return;
}
int mB = 2;
while (mB * mB <= max(x, y)) {
++mB;
}
map<vector<int>, int> mpA;
for (int bx = 2; bx <= A && bx < mB; ++bx) {
vector<int> cur;
int curX = x;
while (curX > 0) {
cur.push_back(curX % bx);
curX /= bx;
}
mpA[cur] = bx;
}
for (int by = 2; by <= B && by < mB; ++by) {
vector<int> cur;
int curY = y;
while (curY > 0) {
cur.push_back(curY % by);
curY /= by;
}
if (mpA.count(cur)) {
cout << "YES\n";
cout << mpA[cur] << ' ' << by << '\n';
return;
}
}
bool sw = false;
if (x < y) {
sw = true;
swap(x, y);
swap(A, B);
}
int diff = x - y;
auto checkD = [&](int n) {
int dab = diff / n;
// a - dab <= B
// a <= B + dab
// a <= A
// a <= x
// a - dab <= y
int a = min({A, B + dab, x / n, y / n + dab, x, y + dab});
debug(n, dab, a);
if (a >= 2) {
int b = a - dab;
if (b >= 2) {
assert(a <= A && b <= B);
debug(x, y, a, b, mB);
if (a * a > x && b * b > y && x % a == y % b && x / a == y / b) {
cout << "YES\n";
if (sw) {
swap(a, b);
}
cout << a << ' ' << b << '\n';
return true;
}
}
}
return false;
};
for (int d = 1; d * d <= diff; ++d) {
if (diff % d == 0) {
if (checkD(d)) return;
if (checkD(diff / d)) return;
}
}
cout << "NO\n";
}
int main() {
#ifdef GOLIKOV
assert(freopen("in", "rt", stdin));
auto _clock_start = chrono::high_resolution_clock::now();
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tests_;
cin >> tests_;
for (int tt_ = 1; tt_ <= tests_; ++tt_) {
solveTest();
}
#ifdef GOLIKOV
cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
chrono::high_resolution_clock::now()
- _clock_start).count() << "ms." << endl;
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3444kb
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: 8ms
memory: 3488kb
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 756 497 YES 17 151 NO YES 182 183 NO YES 86 75 YES 25 10 NO YES 341 413 NO NO NO NO YES 415 145 YES 107 84 YES 15 188 NO NO YES 35 29 YES 12 249 NO NO YES 16 5 YES 151 120 NO YES 750 346 NO YES 67 196 NO YES 66 29 NO NO YES 94 54 YES 6 5 NO NO NO NO NO YES 324 129 NO YES 237 224 YES 17 25 YES 28...
result:
ok correct (1000 test cases)
Test #3:
score: -100
Wrong Answer
time: 252ms
memory: 3568kb
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 18840 23551 YES 742356 748100 NO NO YES 467 521 NO YES 100271 32461 YES 16090 25007 NO YES 139 338 YES 40881 39967 YES 16611 32988 YES 150877 80120 YES 713 699 YES 1381 9024 NO YES 95918 37499 YES 12558 8399 YES 120663 793125 YES 15900 15303 YES 14251 13824 YES 68 138 YES 20932 454...
result:
wrong answer you didn't find a solution but jury did (test case 5)