QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116659#6519. X Equals YITMO_pengzoo#WA 252ms3568kbC++202.6kb2023-06-29 18:32:132023-06-29 18:32:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 18:32:16]
  • 评测
  • 测评结果:WA
  • 用时:252ms
  • 内存:3568kb
  • [2023-06-29 18:32:13]
  • 提交

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)