QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#825595#9770. Middle Pointucup-team4435#WA 0ms3828kbC++235.7kb2024-12-21 20:42:192024-12-21 20:42:24

Judging History

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

  • [2024-12-21 20:42:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3828kb
  • [2024-12-21 20:42:19]
  • 提交

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 || X == 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 rot = 0; rot < 2; ++rot) {
        {
            vector<array<int, 4>> pref;

            for (int i = 0; i < a.size(); ++i) {
                pref.push_back({a[i].first, 0, a[i].second, 0});
                pref.push_back({a[i].first, B, a[i].second, B});
            }
            int x = (a.back().first + a.back().second) / 2;
            for (int i = 0; i < b.size(); ++i) {
                pref.push_back({x, b[i].first, x, b[i].second});
            }
            if (answer.empty() || answer.size() > pref.size()) {
                answer = pref;
                if (rot) {
                    for(auto &t : answer) {
                        swap(t[0], t[1]);
                        swap(t[2], t[3]);
                    }
                }
            }
        }


        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;
                bool ok1 = (b[0].first == ans.back()[1]);
                bool ok2 = (b[0].second == ans.back()[3]);
                for (int i = 0; i < a.size(); ++i) {
                    if ((a[i].first == ans.back()[0]) && (a[i].second == ans.back()[2] || ok2)) break;
                    pref.push_back({a[i].first, 0, a[i].second, 0});
                }
                for (int i = 0; i < a.size(); ++i) {
                    if ((a[i].first == ans.back()[0] || ok1) && (a[i].second == ans.back()[2])) break;
                    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({ans.back()[0], b[i].first, ans.back()[0], b[i].second});
                }
                for (int i = 0; i < b.size(); ++i) {
                    if (b[i].second == ans.back()[3]) break;
                    pref.push_back({ans.back()[2], b[i].first, ans.back()[2], 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]);
                    }
                    if (rot) {
                        for(auto &t : answer) {
                            swap(t[0], t[1]);
                            swap(t[2], t[3]);
                        }
                    }
                }
            }
            for (auto &[l, r]: a) swap(l, r);
        }
        swap(a, b);
        swap(A, B);
    }

    set<array<int, 2>> who;
    who.insert({0, 0});
    who.insert({A, 0});
    who.insert({A, B});
    who.insert({0, B});
    for(auto &t : answer) {
        array<int, 2> F = {t[0], t[1]};
        array<int, 2> S = {t[2], t[3]};
        assert((F[0] + S[0]) % 2 == 0);
        assert((F[1] + S[1]) % 2 == 0);
        assert(who.count(F) && who.count(S));
        auto MID = F;
        MID[0] = (F[0] + S[0]) / 2;
        MID[1] = (F[1] + S[1]) / 2;
        assert(!who.count(MID));
        who.insert(MID);
    }
    assert(who.count({X, Y}));

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

    return 0;
}

詳細信息

Test #1:

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

input:

2 2
1 1

output:

1
0 0 2 2 

result:

ok correct!

Test #2:

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

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

input:

2024 0
1012 0

output:

1
0 0 2024 0

result:

ok correct!

Test #5:

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

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

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

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

input:

2024 2026
2024 2026

output:

0

result:

ok correct!

Test #8:

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

input:

1000000000 1000000000
70 0

output:

-1

result:

ok correct!

Test #9:

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

input:

3 6
2 4

output:

-1

result:

ok correct!

Test #10:

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

input:

7 7
7 2

output:

-1

result:

ok correct!

Test #11:

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

input:

6 2
5 2

output:

-1

result:

ok correct!

Test #12:

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

input:

5 7
5 5

output:

-1

result:

ok correct!

Test #13:

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

input:

4 7
2 3

output:

-1

result:

ok correct!

Test #14:

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

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

input:

3 3
0 2

output:

-1

result:

ok correct!

Test #16:

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

input:

7 7
1 4

output:

-1

result:

ok correct!

Test #17:

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

input:

6 3
6 1

output:

-1

result:

ok correct!

Test #18:

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

input:

4 2
2 1

output:

1
0 0 4 2 

result:

ok correct!

Test #19:

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

input:

7 2
3 2

output:

-1

result:

ok correct!

Test #20:

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

input:

2 7
0 3

output:

-1

result:

ok correct!

Test #21:

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

input:

1 7
1 0

output:

0

result:

ok correct!

Test #22:

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

input:

5 1
0 0

output:

0

result:

ok correct!

Test #23:

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

input:

8 7
4 3

output:

-1

result:

ok correct!

Test #24:

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

input:

180057652 674822131
110693180 428023738

output:

-1

result:

ok correct!

Test #25:

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

input:

62347541 812142018
42922107 486416913

output:

-1

result:

ok correct!

Test #26:

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

input:

239604722 244429197
78993837 108804105

output:

-1

result:

ok correct!

Test #27:

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

input:

416861903 381749084
375027630 373683256

output:

-1

result:

ok correct!

Test #28:

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

input:

594119084 519068971
429116021 298715088

output:

-1

result:

ok correct!

Test #29:

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

input:

536870912 536870912
233225286 372408647

output:

85
0 0 536870912 0 
0 536870912 536870912 536870912 
0 0 268435456 0 
0 536870912 268435456 536870912 
134217728 0 268435456 0 
134217728 536870912 268435456 536870912 
201326592 0 268435456 0 
201326592 536870912 268435456 536870912 
201326592 0 234881024 0 
201326592 536870912 234881024 536870912 ...

result:

wrong answer Jury has a better answer