제출 #527814

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527814		KoD	Izvanzemaljci (COI21_izvanzemaljci)	C++17	26 / 100	53 ms	8636 KiB

izvanzemaljci

#include <bits/stdc++.h>

using std::vector;
using std::array;
using std::pair;
using std::tuple;

using ll = long long;

constexpr ll inf = 2000000000 + 10;

using Point = array<ll, 2>;
using Rect = array<ll, 4>;

ll length(const Rect& r) {
    return std::max({r[1] - r[0], r[3] - r[2], 1ll});
}

Rect identity() {
    return {inf, -inf, inf, -inf};
}

Rect to_rect(const Point& p) {
    return {p[0], p[0], p[1], p[1]};
}

Rect merge(const Rect& a, const Rect& b) {
    return {std::min(a[0], b[0]), std::max(a[1], b[1]), std::min(a[2], b[2]), std::max(a[3], b[3])};
}

pair<Rect, Rect> split(vector<Point> pts) {
    const int n = pts.size();
    std::sort(pts.begin(), pts.end(), [&](const Point& p, const Point& q) {
        return p[0] < q[0];
    });
    vector<Rect> suff(n + 1);
    suff[n] = identity();
    for (int i = n - 1; i >= 0; --i) {
        suff[i] = merge(to_rect(pts[i]), suff[i + 1]);
    }
    const auto all = suff[0];
    if (all[0] == all[1]) {
        return {all, {all[0] - 2, all[0] - 1, all[2], all[2] + 1}};
    }
    Rect a, b, left = identity();
    ll len = inf;
    for (int i = 0; i < n;) {
        int j = i;
        while (j < n and pts[i][0] == pts[j][0]) {
            left = merge(left, to_rect(pts[j]));
            j += 1;
        }
        i = j;
        if (i == n) {
            break;
        }
        if (len > std::max(length(left), length(suff[i]))) {
            a = {left[1] - length(left), left[1], left[2], left[2] + length(left)};
            b = suff[i];
            len = std::max(length(left), length(suff[i]));
        }
    }
    return {a, b};
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int N, K;
    std::cin >> N >> K;
    vector<Point> P(N);
    for (auto& [x, y] : P) {
        std::cin >> x >> y;
    }

    if (K == 1) {
        Rect r = identity();
        for (const auto& p : P) {
            r = merge(r, to_rect(p));
        }
        std::cout << r[0] << ' ' << r[2] << ' ' << length(r) << '\n';
        return 0;
    }

    if (K == 2) {
        auto [a, b] = split(P);
        for (auto& [x, y] : P) std::swap(x, y);
        auto [c, d] = split(P);
        std::swap(c[0], c[2]);
        std::swap(c[1], c[3]);
        std::swap(d[0], d[2]);
        std::swap(d[1], d[3]);
        if (std::max(length(a), length(b)) < std::max(length(c), length(d))) {
            std::cout << a[0] << ' ' << a[2] << ' ' << length(a) << '\n';
            std::cout << b[0] << ' ' << b[2] << ' ' << length(b) << '\n';
        } else {
            std::cout << c[0] << ' ' << c[2] << ' ' << length(c) << '\n';
            std::cout << d[0] << ' ' << d[2] << ' ' << length(d) << '\n';
        }
        return 0;
    }
    
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 0 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32