QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#841702#9770. Middle PointarcaML 0ms3832kbC++201.8kb2025-01-03 22:55:572025-01-03 22:55:57

Judging History

This is the latest submission verdict.

  • [2025-01-03 22:55:57]
  • Judged
  • Verdict: ML
  • Time: 0ms
  • Memory: 3832kb
  • [2025-01-03 22:55:57]
  • Submitted

answer

#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;

using i64 = long long;

i64 A, B, x, y;
vector<pair<i64, i64>> s;
set<pair<i64, i64>> E;

int main() {
    cin >> A >> B >> x >> y;

    s.push_back({0, 0});
    s.push_back({A, 0});
    s.push_back({0, B});
    s.push_back({A, B});
    E = set(s.begin(), s.end());

    // Check
    if (E.contains({x, y})) {
        cout << 0 << "\n";
        return 0;
    }
    if (A == 0 && B == 0 && (x != 0 || y != 0)) {
        cout << -1 << '\n';
        return 0;
    }
    {
        i64 d1, c1, d2, c2;
        for (d1 = 0, c1 = -1; A && (1ll << d1) <= A; d1++) {
            if ((1ll << d1) * x % A == 0) {
                c1 = (1ll << d1) * x / A;
                break;
            }
        }
        for (d2 = 0, c2 = -1; B && (1ll << d2) <= B; d2++) {
            if ((1ll << d2) * y % B == 0) {
                c2 = (1ll << d2) * y / B;
                break;
            }
        }
        if (c1 == -1 && c2 == -1) {
            cout << -1 << '\n';
            return 0;
        }
    }

    using P = pair<i64, i64>;

    auto dist = [&](P &a, i64 b, i64 c) {
        return (a.first - b) * (a.first - b) +
               (a.second - c) * (a.second - c);
    };
    int dep  = 0;
    auto dfs = [&](auto f, i64 a, i64 b) -> void {
        sort(s.begin(), s.end(), [&](P &a1, P &b1) {
            return dist(a1, a, b) < dist(b1, a, b);
        });

        auto [l, r] = s[0];
        int nl = a * 2 - l, nr = b * 2 - r;

        dep++;
        if (!E.contains({nl, nr})) f(f, nl, nr);
        else cout << dep << "\n";

        if (dep) cout << nl << " " << nr << " " << l << " " << r << '\n';
    };

    dfs(dfs, x, y);
}

詳細信息

Test #1:

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

input:

2 2
1 1

output:

1
2 2 0 0

result:

ok correct!

Test #2:

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

input:

8 8
5 0

output:

3
8 0 0 0
4 0 0 0
2 0 8 0

result:

ok correct!

Test #3:

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

input:

0 0
0 0

output:

0

result:

ok correct!

Test #4:

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

input:

2024 0
1012 0

output:

1
2024 0 0 0

result:

ok correct!

Test #5:

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

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

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

input:

8 6
7 3

output:

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

result:

ok correct!

Test #7:

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

input:

2024 2026
2024 2026

output:

0

result:

ok correct!

Test #8:

score: -100
Memory Limit Exceeded

input:

1000000000 1000000000
70 0

output:


result: