QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#863021#9770. Middle PointMonkeyKingTL 0ms0kbC++143.9kb2025-01-19 11:45:582025-01-19 11:46:03

Judging History

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

  • [2025-01-19 11:46:03]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2025-01-19 11:45:58]
  • 提交

answer

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
    ll A, B, X, Y;
    cin >> A >> B;
    cin >> X >> Y;

    vector<pair<pll, pll>> operations;

    // Function to generate sequence of operations for coordinate
    auto generate_operations = [](ll coord_max, ll target_coord) -> vector<pll> {
        vector<pll> ops;
        if (coord_max % 2 != 0) {
            // Only 0 and coord_max are possible
            if (target_coord != 0 && target_coord != coord_max) {
                ops.push_back({-1, -1});
                return ops;
            } else {
                return ops;
            }
        } else {
            ll L = 0, R = coord_max;
            while (L != target_coord) {
                ll M = (L + R) / 2;
                ops.push_back({L, R});
                if (target_coord <= M) {
                    R = M;
                } else {
                    L = M;
                }
            }
            return ops;
        }
    };

    vector<pll> x_ops, y_ops;
    if (A % 2 == 1) {
        if (X != 0 && X != A) {
            cout << -1 << endl;
            return 0;
        }
    } else {
        x_ops = generate_operations(A, X);
        if (!x_ops.empty() && x_ops[0].first == -1) {
            cout << -1 << endl;
            return 0;
        }
    }
    if (B % 2 == 1) {
        if (Y != 0 && Y != B) {
            cout << -1 << endl;
            return 0;
        }
    } else {
        y_ops = generate_operations(B, Y);
        if (!y_ops.empty() && y_ops[0].first == -1) {
            cout << -1 << endl;
            return 0;
        }
    }

    vector<pll> points; // List of points currently in S
    set<pll> point_set;
    if (A != 0 && B != 0) {
        points.push_back({0, 0});
        points.push_back({0, B});
        points.push_back({A, 0});
        points.push_back({A, B});
    } else if (A == 0 && B != 0) {
        points.push_back({0, 0});
        points.push_back({0, B});
    } else if (A != 0 && B == 0) {
        points.push_back({0, 0});
        points.push_back({A, 0});
    } else {
        points.push_back({0, 0});
    }
    for (auto p : points) {
        point_set.insert(p);
    }

    vector<pair<pll, pll>> total_ops;

    // Map to find points with particular x or y
    map<ll, pll> x_to_point, y_to_point;
    for (auto p : points) {
        x_to_point[p.first] = p;
        y_to_point[p.second] = p;
    }

    // Process x operations
    for (auto op : x_ops) {
        ll Lx = op.first, Rx = op.second;
        pll P = x_to_point[Lx];
        pll Q = x_to_point[Rx];
        // For y, take any existing y-coordinate (we can choose any since it's arbitrary)
        pll new_point = {(Lx + Rx) / 2, P.second};
        total_ops.push_back({P, Q});
        x_to_point[(Lx + Rx) / 2] = new_point;
        if (point_set.find(new_point) == point_set.end()) {
            points.push_back(new_point);
            point_set.insert(new_point);
        }
    }
    // Process y operations
    for (auto op : y_ops) {
        ll Ly = op.first, Ry = op.second;
        pll P = y_to_point[Ly];
        pll Q = y_to_point[Ry];
        // For x, take any existing x-coordinate (we can choose any since it's arbitrary)
        pll new_point = {P.first, (Ly + Ry) / 2};
        total_ops.push_back({P, Q});
        y_to_point[(Ly + Ry) / 2] = new_point;
        if (point_set.find(new_point) == point_set.end()) {
            points.push_back(new_point);
            point_set.insert(new_point);
        }
    }

    cout << total_ops.size() << endl;
    for (auto op : total_ops) {
        cout << op.first.first << " " << op.first.second << " "
             << op.second.first << " " << op.second.second << endl;
    }

    return 0;
}

詳細信息

Test #1:

score: 0
Time Limit Exceeded

input:

2 2
1 1

output:


result: