QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#704706	#6519. X Equals Y	lllei^#	WA	5ms	3704kb	C++20	2.7kb	2024-11-02 20:41:34	2024-11-02 20:41:35

Judging History

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

[2024-11-02 20:41:35]
评测

测评结果：WA
用时：5ms
内存：3704kb

查看

[2024-11-02 20:41:34]
提交

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, A); i++)
        {
            int cur = 0, t = x;
            while (t)
            {
                cur = (cur * 1LL * bas + t % i) % mod;
                t = t / i;
            }
            mp[cur] = i;
        }
        for (int i = 2; i <= min(lim, B); i++)
        {
            int cur = 0, t = y;
            while (t)
            {
                cur = (cur * 1LL * bas + t % i) % mod;
                t = t / i;
            }
            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;
        for (int l1 = A, l2 = min(y / (x / A), 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";
    }
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3528kb

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: -100

Wrong Answer

time: 5ms

memory: 3704kb

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
31 215
NO
YES
289 291
NO
YES
86 75
YES
25 10
YES
291 14
YES
341 413
YES
211 37
NO
YES
235 43
NO
YES
7 13
YES
107 84
YES
15 188
NO
YES
19 18
YES
282 39
YES
4 7
NO
YES
151 27
YES
16 5
YES
151 120
NO
YES
750 346
NO
YES
67 196
NO
YES
66 29
NO
NO
YES
698 63
YES
6 5
NO
YES
28 95
NO
YES
307...

result:

wrong answer wrong solution, (52 in base 31) != (454 in base 215) (test case 2)