QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#825200#9770. Middle Pointucup-team4435#WA 1ms3836kbC++234.6kb2024-12-21 17:42:172024-12-21 17:42:19

Judging History

This is the latest submission verdict.

  • [2024-12-21 17:42:19]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3836kb
  • [2024-12-21 17:42:17]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    auto work = [&](int A, int X) -> vector<pair<int, int>> {
        if (A == X || A == 0) {
            return {};
        }
        int p = 1;
        while (A % 2 == 0) {
            p *= 2;
            A /= 2;
        }
        int f = A;
        if (X % f != 0) {
            return {{-1, -1}};
        }
        X /= f;
        A = p;
        vector<pair<int, int>> o;
        int l = 0, r = A;
        while (l != X && r != X) {
            int mid = l + r >> 1;
            o.push_back({l, r});
            if (mid == X) {
                break;
            } else if (mid > X) {
                r = mid;
            } else {
                l = mid;
            }
        }
        for (auto &[x, y]: o) {
            x *= f, y *= f;
        }
        return o;
    };

    int A, B, X, Y;
    cin >> A >> B >> X >> Y;

    auto a = work(A, X), b = work(B, Y);
    if (!a.empty() && a[0].first == -1 || !b.empty() && b[0].first == -1) {
        cout << "-1\n";
        return 0;
    }

    if (a.empty() || b.empty()) {
        int i = 0;
        cout << max(a.size(), b.size()) << '\n';
        while (i < a.size() || i < b.size()) {
            int x1 = X, y1 = Y, x2 = X, y2 = Y;
            if (i < a.size()) {
                x1 = a[i].first, x2 = a[i].second;
            }
            if (i < b.size()) {
                y1 = b[i].first, y2 = b[i].second;
            }
            i += 1;
            cout << x1 << " " << y1 << " " << x2 << " " << y2 << '\n';
        }
        return 0;
    }

    vector<array<int, 4>> answer;

    for(int it = 0; it < 2; ++it) {
        vector<array<int, 4>> ans;
        ans.push_back({a.back().first, b.back().first, a.back().second, b.back().second});
        int pos = 1;
        while (pos < a.size() && pos < b.size()) {
            int pa = (int)a.size() - pos - 1;
            int pb = (int)b.size() - pos - 1;
            if (a[pa].first == a[pa+1].first) {
                if (b[pb].first != b[pb+1].first) break;
            } else {
                assert(a[pa].second == a[pa + 1].second);
                if (b[pb].second != b[pb + 1].second) break;
            }
            ans.push_back({a[pa].first, b[pb].first, a[pa].second, b[pb].second});
            pos++;
        }

        {
            vector<array<int, 4>> pref;
            for(int i = 0; i < a.size(); ++i) {
                if (a[i].first == ans.back()[0] && a[i].second == ans.back()[2]) break;
                pref.push_back({a[i].first, 0, a[i].second, 0});
                pref.push_back({a[i].first, B, a[i].second, B});
            }
            for(int i = 0; i < b.size(); ++i) {
                if (b[i].first == ans.back()[1]) break;
                pref.push_back({a[i].first, b[i].first, a[i].first, b[i].second});
            }
            for(int i = 0; i < b.size(); ++i) {
                if (b[i].second == ans.back()[3]) break;
                pref.push_back({a[i].second, b[i].first, a[i].second, b[i].second});
            }

            if (answer.empty() || answer.size() > pref.size() + ans.size()) {
                answer = pref;
                for(int t = (int)ans.size() - 1; t >= 0; --t) {
                    answer.push_back(ans[t]);
                }
            }
        }
        {
            vector<array<int, 4>> pref;
            for(int i = 0; i < b.size(); ++i) {
                if (b[i].first == ans.back()[1] && b[i].second == ans.back()[3]) break;
                pref.push_back({0, b[i].first, 0, b[i].second});
                pref.push_back({A, b[i].first, A, b[i].second});
            }
            for(int i = 0; i < a.size(); ++i) {
                if (a[i].first == ans.back()[0]) break;
                pref.push_back({a[i].first, b[i].first, a[i].second, b[i].first});
            }
            for(int i = 0; i < a.size(); ++i) {
                if (a[i].second == ans.back()[2]) break;
                pref.push_back({a[i].first, b[i].second, a[i].second, b[i].second});
            }


            if (answer.empty() || answer.size() > pref.size() + ans.size()) {
                answer = pref;
                for(int t = (int)ans.size() - 1; t >= 0; --t) {
                    answer.push_back(ans[t]);
                }
            }
        }
        for(auto &[l, r] : a) swap(l, r);
    }

    cout << answer.size() << '\n';
    for(auto &t : answer) {
        for(auto &x : t) cout << x << ' ';
        cout << '\n';
    }

    return 0;
}

详细

Test #1:

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

input:

2 2
1 1

output:

1
0 0 2 2 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

8 8
5 0

output:

3
0 0 8 0
4 0 8 0
4 0 6 0

result:

ok correct!

Test #3:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

0 0
0 0

output:

0

result:

ok correct!

Test #4:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2024 0
1012 0

output:

1
0 0 2024 0

result:

ok correct!

Test #5:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

8 6
7 3

output:

3
0 0 8 0 
4 0 8 0 
6 0 8 6 

result:

ok correct!

Test #7:

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

input:

2024 2026
2024 2026

output:

0

result:

ok correct!

Test #8:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

1000000000 1000000000
70 0

output:

-1

result:

ok correct!

Test #9:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

3 6
2 4

output:

-1

result:

ok correct!

Test #10:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

7 7
7 2

output:

-1

result:

ok correct!

Test #11:

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

input:

6 2
5 2

output:

-1

result:

ok correct!

Test #12:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

5 7
5 5

output:

-1

result:

ok correct!

Test #13:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4 7
2 3

output:

-1

result:

ok correct!

Test #14:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

8 2
2 2

output:

2
0 2 8 2
0 2 4 2

result:

ok correct!

Test #15:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

3 3
0 2

output:

-1

result:

ok correct!

Test #16:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

7 7
1 4

output:

-1

result:

ok correct!

Test #17:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

6 3
6 1

output:

-1

result:

ok correct!

Test #18:

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

input:

4 2
2 1

output:

1
0 0 4 2 

result:

ok correct!

Test #19:

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

input:

7 2
3 2

output:

-1

result:

ok correct!

Test #20:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

2 7
0 3

output:

-1

result:

ok correct!

Test #21:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

1 7
1 0

output:

0

result:

ok correct!

Test #22:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

5 1
0 0

output:

0

result:

ok correct!

Test #23:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

8 7
4 3

output:

-1

result:

ok correct!

Test #24:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

180057652 674822131
110693180 428023738

output:

-1

result:

ok correct!

Test #25:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

62347541 812142018
42922107 486416913

output:

-1

result:

ok correct!

Test #26:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

239604722 244429197
78993837 108804105

output:

-1

result:

ok correct!

Test #27:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

416861903 381749084
375027630 373683256

output:

-1

result:

ok correct!

Test #28:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

594119084 519068971
429116021 298715088

output:

-1

result:

ok correct!

Test #29:

score: -100
Wrong Answer
time: 0ms
memory: 3628kb

input:

536870912 536870912
233225286 372408647

output:

105
0 0 0 536870912 
536870912 0 536870912 536870912 
0 268435456 0 536870912 
536870912 268435456 536870912 536870912 
0 268435456 0 402653184 
536870912 268435456 536870912 402653184 
0 335544320 0 402653184 
536870912 335544320 536870912 402653184 
0 369098752 0 402653184 
536870912 369098752 536...

result:

wrong answer (268435456,268435456) is not in S