QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#325545#6519. X Equals YLainWA 9ms3828kbC++234.8kb2024-02-11 16:36:192024-02-11 16:36:20

Judging History

你现在查看的是最新测评结果

  • [2024-02-11 16:36:20]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3828kb
  • [2024-02-11 16:36:19]
  • 提交

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)