QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#325545 | #6519. X Equals Y | Lain | WA | 9ms | 3828kb | C++23 | 4.8kb | 2024-02-11 16:36:19 | 2024-02-11 16:36:20 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
int gcd(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = gcd(b, a % b, x1, y1);
x = y1;
y = x1 - y1 * (a / b);
return d;
}
bool find_any_solution(int a, int b, int c, int &x0, int &y0, int &g) {
g = gcd(abs(a), abs(b), x0, y0);
if (c % g) {
return false;
}
x0 *= c / g;
y0 *= c / g;
if (a < 0) x0 = -x0;
if (b < 0) y0 = -y0;
return true;
}
void shift_solution(int & x, int & y, int a, int b, int cnt) {
x += cnt * b;
y -= cnt * a;
}
const int INF = -1e9;
int find_all_solutions(int a, int b, int c, int minx, int maxx, int miny, int maxy) {
int x, y, g;
if (!find_any_solution(a, b, c, x, y, g))
return INF;
a /= g;
b /= g;
int sign_a = a > 0 ? +1 : -1;
int sign_b = b > 0 ? +1 : -1;
shift_solution(x, y, a, b, (minx - x) / b);
if (x < minx)
shift_solution(x, y, a, b, sign_b);
if (x > maxx)
return INF;
int lx1 = x;
shift_solution(x, y, a, b, (maxx - x) / b);
if (x > maxx)
shift_solution(x, y, a, b, -sign_b);
int rx1 = x;
shift_solution(x, y, a, b, -(miny - y) / a);
if (y < miny)
shift_solution(x, y, a, b, -sign_a);
if (y > maxy)
return INF;
int lx2 = x;
shift_solution(x, y, a, b, -(maxy - y) / a);
if (y > maxy)
shift_solution(x, y, a, b, sign_a);
int rx2 = x;
if (lx2 > rx2)
swap(lx2, rx2);
int lx = max(lx1, lx2);
int rx = min(rx1, rx2);
if (lx > rx)
return INF;
return lx;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int tt;
cin >> tt;
while(tt--) {
int x, y, a, b;
cin >> x >> y >> a >> b;
if (x== y) {
cout << "YES\n";
cout << 2 << " " << 2 << '\n';
continue;
}
a = min(a, x);
b = min(b, y);
struct Line {
int m, c;
int l, r;
};
map<vector<int>, int> Xprop, Yprop;
map<int, Line> Xlines, Ylines;
auto conv = [&](int x, int base)->vector<int> {
vector<int> ret;
while(x) {
ret.push_back(x%base);
x /= base;
}
reverse(ret.begin(), ret.end());
return ret;
};
for (int i = 2; i <= a; i++) {
if (x/i < i) {
// two digit
int tens = x/i;
Xlines[tens] = Line{-tens, x, i, x/tens};
i = x/tens;
} else {
Xprop[conv(x, i)] = i;
}
}
for (int i = 2; i <= b; i++) {
if (y/i < i) {
// two digit
int tens = y/i;
Ylines[tens] = Line{-tens, y, i, y/tens};
i = y/tens;
} else {
Yprop[conv(y, i)] = i;
}
}
for (auto& [value, base] : Xprop) {
// prop-prop intersection
{
auto it = Yprop.find(value);
if (it != Yprop.end()) {
cout << "YES\n";
cout << base << " " << it->second << '\n';
goto end;
}
}
// line-prop intersection
{
if (value.size() == 2) {
auto it = Ylines.find(value[0]);
if (it != Ylines.end()) {
int want = value[1];
if ((want - it->second.c)%it->second.m == 0) {
int X = (want - it->second.c)/it->second.m;
if (X >= it->second.l && X <= it->second.r) {
cout << "YES\n";
cout << base << " " << X << '\n';
goto end;
}
}
}
}
}
}
// line-prop intersection
for (auto& [value, base] : Yprop) {
if (value.size() == 2) {
auto it = Xlines.find(value[0]);
if (it != Xlines.end()) {
int want = value[1];
if ((want - it->second.c)%it->second.m == 0) {
int X = (want - it->second.c)/it->second.m;
if (X >= it->second.l && X <= it->second.r) {
cout << "YES\n";
cout << X << " " << base << '\n';
goto end;
}
}
}
}
}
// line-line intersection
for (auto& [tens, line] : Xlines) {
auto it = Ylines.find(tens);
if (it != Ylines.end()) {
int C = x-y;
int A = tens;
int B = -it->first;
int res = find_all_solutions(A, B, C, line.l, line.r, it->second.l, it->second.r);
if (res != INF) {
int xbase = res;
int ybase = (C - A*xbase)/B;
cout << "YES\n";
cout << xbase << " " << ybase << '\n';
goto end;
}
}
}
cout << "NO\n";
end:;
}
}
// For b < sqrt(y), find the actual values.
// For b > sqrt(y), it is always two digits of the form Ax, where x is some linear function in a range
// Check for intersections.
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3828kb
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: -100
Wrong Answer
time: 9ms
memory: 3620kb
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 18 219 NO YES 244 246 NO YES 340 263 YES 26 11 NO YES 214 286 NO YES 67 26 NO NO YES 406 136 YES 96 73 YES 12 185 NO YES 356 13 YES 45 37 YES 20 731 NO NO YES 16 5 YES 132 101 NO YES 701 297 YES 78 839 YES 68 326 NO YES 65 28 YES 297 44 NO YES 89 49 YES 6 5 NO NO NO NO NO YES 520 130...
result:
wrong answer Integer parameter [name=b] equals to 219, violates the range [2, 218] (test case 2)