QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142626#6519. X Equals YBUET_POTATOES#WA 3ms3484kbC++202.1kb2023-08-19 14:23:072023-08-19 14:23:10

Judging History

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

  • [2023-08-19 14:23:10]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3484kb
  • [2023-08-19 14:23:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

vector<int> get(int x, int a){
    vector<int> res;
    while(x){
        res.push_back(x % a);
        x /= a;
    }
    return res;
}

void solve(){
    int x, y, A, B;
    cin>>x>>y>>A>>B;

    if(x == 1 || y == 1){
        if(x == y){
            cout<<"YES\n";
            cout<<"2 2\n";
        }
        else{
            cout<<"NO\n";
        }
        return;
    }

    if(x <= A && y <= B){
        cout<<"YES\n";
        cout<<x<<" "<<y<<"\n";
        return;
    }

    A = min(A, x-1);
    B = min(B, y-1);
    int loA = 2, loB = 2;

    map<vector<int>, int> mp;

    for(int a = 2; a*a <= x && a <= A; a++){
        mp[get(x, a)] = a;
        loA = a+1;
    }

    for(int b = 2; b*b <= y && b <= B; b++){
        auto v = get(y,b);
        if(mp.count(v) > 0){
            int a = mp[v];

            cout<<"YES\n";
            cout<<a<< " " <<b<<"\n";
            return;
        }
        loB = b+1;
    }

    /// p*a+q = x, p*b+q = y

    for(int p = 1; p*p < min(x, y); p++){
        if((x-y) % p != 0){
            continue;
        }

        if(x < y){
            int del = (y-x)/p;
            /// b = a+del

            int l = max(loA, loB-del);
            int r = min(A, B-del);

            l = max(l, x/(p+1)+1);
            r = min(r, x/p);

            if(l > r) continue;

            cout<<"YES\n";
            cout<<l<<" "<<l+del<<"\n";
        }
        else{
            int del = (x-y)/p;
            /// b+del = a

            int l = max(loB, loA-del);
            int r = min(B, A-del);

            l = max(l, y/(p+1)+1);
            r = min(r, y/p);

            if(l > r) continue;

            cout<<"YES\n";
            cout<<l+del<<" "<<l<<"\n";
        }
    }

    cout<<"NO\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int tc;
    cin>>tc;

    for(int cs = 1; cs <= tc; cs++){
        solve();
    }

    return 0;
}

/*
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
*/

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3468kb

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: 3484kb

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
120 83
NO
YES
14 148
YES
8 75
NO
NO
YES
244 246
YES
146 147
NO
NO
YES
77 66
YES
51 44
NO
YES
25 10
NO
YES
214 286
YES
143 179
YES
107 131
YES
86 104
YES
61 73
YES
48 57
YES
43 51
YES
33 39
YES
23 27
NO
NO
NO
NO
NO
YES
406 136
YES
282 102
YES
217 82
YES
176 68
YES
148 58
YES
101 41
YE...

result:

wrong answer Integer parameter [name=a] equals to 120, violates the range [2, 31] (test case 2)