QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704749#6519. X Equals Ylllei#WA 702ms6632kbC++203.0kb2024-11-02 20:54:082024-11-02 20:54:10

Judging History

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

  • [2024-11-02 20:54:10]
  • 评测
  • 测评结果:WA
  • 用时:702ms
  • 内存:6632kb
  • [2024-11-02 20:54:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int bas = 1333331;
int T;
map<int, int> mp;
pair<int, int> pii;
bool check(int l1, int r1, int l2, int r2, int d)
{
    // cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<endl;
    if (l1 % d != l2 % d)
        return false;
    if (r1 < l2 || l1 > r2)
        return false;
    if (l2 <= l1 && l1 <= r2)
    {
        pii = {0, (l1 - l2) / d};
        return true;
    }
    if (l2 <= r1 && r1 <= r2)
    {
        pii = {(r1 - l1) / d, (r1 - l2) / d};
        return true;
    }
    if (l1 <= l2 && l2 <= r1)
    {
        pii = {(l2 - l1) / d, 0};
        return true;
    }
    if (l1 <= r2 && r2 <= r1)
    {
        pii = {(r2 - l1) / d, (r2 - l2) / d};
        return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        mp.clear();
        int x, y, A, B, flg = 0;
        cin >> x >> y >> A >> B;
        int lim = sqrt(max(x, y));
        for (int i = 2; i <= min(lim + 1, A); i++)
        {
            int cur = 0, t = x;
            vector<int> num;
            while (t)
            {
                num.push_back(t % i);
                t = t / i;
            }
            reverse(num.begin(), num.end());
            for (auto cc : num)
                cur = (cur * 1LL * bas + cc) % mod;
            mp[cur] = i;
        }
        for (int i = 2; i <= min(lim + 1, B); i++)
        {
            int cur = 0, t = y;
            vector<int> num;
            while (t)
            {
                num.push_back(t % i);
                t = t / i;
            }
            reverse(num.begin(), num.end());
            for (auto cc : num)
                cur = (cur * 1LL * bas + cc) % mod;
            if (mp[cur])
            {
                cout << "YES\n";
                cout << mp[cur] << ' ' << i << '\n';
                flg = 1;
                break;
            }
        }
        if (flg)
            continue;
        if (x == y && A > x && B > y)
        {
            cout << "YES\n";
            cout << x + 1 << ' ' << y + 1 << '\n';
            continue;
        }
        A = min(x, A);
        B = min(y, B);
        // cout << A << ' ' << B << endl;
        int tt=max(x/A,y/B);
        for (int l1 = min(x/tt,A), l2 = min(y/tt, B), r1, r2; l1 >= 1 && l2 >= 1; l1 = r1 - 1, l2 = r2 - 1)
        {
            if (x / l1 >= l1)
                break;
            if (y / l2 >= l2)
                break;
            r1 = x / (x / l1 + 1) + 1;
            r2 = y / (y / l2 + 1) + 1;
            // cout << x / l1<<' '<<y/l2 << endl;
            // cout<<l1<<' '<<l2<<endl;
            if (check(x % l1, x % r1, y % l2, y % r2, x / l1))
            {
                cout << "YES\n";
                cout << l1 - pii.first << ' ' << l2 - pii.second << '\n';
                flg = 1;
                break;
            }
        }
        if (!flg)
            cout << "NO\n";
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

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: 3ms
memory: 3516kb

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
289 291
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
47 39
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: 0
Accepted
time: 240ms
memory: 3832kb

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
235254 230765
YES
37680 47102
YES
472763 478507
NO
YES
107936 102069
YES
467 521
YES
288042 234973
YES
253276 49846
YES
84403 137905
YES
387516 699627
YES
139 338
YES
40881 39967
YES
16611 32988
YES
344148 131877
YES
713 699
YES
1381 9024
NO
YES
536175 185661
YES
138141 92392
YES
109907 782369
Y...

result:

ok correct (1000 test cases)

Test #4:

score: -100
Wrong Answer
time: 702ms
memory: 6632kb

input:

1000
981241785 906230829 601363803 626653490
197057696 698550046 128696358 449956015
182548925 796382933 101642956 339324198
816288818 177783961 308532802 32376477
628394197 777548138 355072973 757299936
599075146 752655475 473746059 323396924
261214299 95047810 181049121 60329182
7484303 329571035 ...

output:

YES
23170 23082
YES
7140 13806
YES
2644 481
YES
11612 5330
YES
11019 12059
YES
25023 15274
YES
10528 6353
YES
2685 16669
YES
1796495 1768498
YES
2335 2446
YES
18219 17340
YES
23225 30
YES
9529 25632
YES
20848 20964
YES
9371 11368
YES
16778 6486
YES
12005 5889
YES
13362 12047
YES
8141 11971
YES
19972...

result:

wrong answer wrong solution, (981241785 in base 23170) != (906230829 in base 23082) (test case 1)