QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#359031	#6519. X Equals Y	PorNPtree	WA	3ms	3844kb	C++14	2.4kb	2024-03-20 11:14:27	2024-03-20 11:14:27

Judging History

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

[2024-03-20 11:14:27]
评测

测评结果：WA
用时：3ms
内存：3844kb

查看

[2024-03-20 11:14:27]
提交

answer

#include <bits/stdc++.h>

using namespace std;

const int B = 71;

signed main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        int x, y, A, B;
        scanf("%d%d%d%d", &x, &y, &A, &B);
        if (x == y) {
            puts("YES");
            puts("2 2");
        } else if (x == 1 || y == 1) {
            puts("NO");
        } else {
            unordered_map<unsigned long long, int> M;
            for (int i = 2; i * i <= x && i <= A; ++i) {
                unsigned long long z = 0, tz = x;
                while (tz) {
                    z = (__uint128_t)z * B + tz % i;
                    tz /= i;
                }
                M[z] = i;
            }
            int flg = 0;
            for (int i = 2; i * i <= y && i <= B; ++i) {
                unsigned long long z = 0, tz = y;
                while (tz) {
                    z = (__uint128_t)z * B + tz % i;
                    tz /= i;
                }
                if (M.count(z)) {
                    puts("YES");
                    printf("%d %d\n", M[z], i);
                    flg = 1;
                    break;
                }
            }
            if (!flg) {
                unordered_map<int, pair<int, int> > M;
                for (int i = ceil(sqrt(x) + 1e-6), j; i <= A && i <= x; i = j + 1) {
                    j = x / (x / i);
                    M[x / i] = make_pair(i, j);
                }
                for (int i = ceil(sqrt(y) + 1e-6), j; i <= B && i <= y; i = j + 1) {
                    j = y / (y / i);
                    if (M.count(y / i)) {
                        int l1 = M[y / i].first, r1 = M[y / i].second;
                        int l2 = i, r2 = j, V = (y - x) / (y / i);
                        if (l2 - r1 <= V && r2 - l1 >= V) {
                            puts("YES");
                            int dl = V - (l2 - r1);
                            if (dl <= r2 - l2) {
                                printf("%d %d\n", r1, l2 + dl);
                            } else {
                                printf("%d %d\n", r1 - (dl - (r2 - l2)), r2);
                            }
                            flg = 1;
                            break;
                        }
                    }
                }
                if (!flg) {
                    puts("NO");
                }
            }
        }
    }
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3788kb

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: 3ms

memory: 3844kb

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
36 26
YES
8 75
NO
YES
28 28
YES
13 53
YES
28 25
YES
25 10
YES
97 11
YES
21 24
YES
21 36
YES
14 8
YES
49 20
YES
27 30
YES
7 13
YES
29 23
YES
7 93
NO
YES
144 7
YES
26 22
YES
4 7
NO
YES
14 17
YES
16 5
YES
31 25
YES
15 27
YES
42 25
YES
14 83
YES
12 35
YES
82 13
YES
45 20
YES
63 13
YES
11 42
YES
37 2...

result:

wrong answer wrong solution, (920 in base 36) != (661 in base 26) (test case 1)