oj.uz

Submission #527814

# Submission time Handle Problem Language Result Execution time Memory
527814 2022-02-18T12:02:30 Z KoD Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 53 ms 8636 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 22 ms 3796 KB Output is correct
8 Correct 24 ms 3776 KB Output is correct
9 Correct 23 ms 3888 KB Output is correct
10 Correct 28 ms 3904 KB Output is correct
11 Correct 20 ms 3780 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 41 ms 8560 KB Output is correct
11 Correct 40 ms 8572 KB Output is correct
12 Correct 53 ms 8636 KB Output is correct
13 Correct 40 ms 8560 KB Output is correct
14 Correct 43 ms 8572 KB Output is correct
15 Correct 47 ms 8560 KB Output is correct
16 Correct 42 ms 8568 KB Output is correct
17 Correct 35 ms 7820 KB Output is correct
18 Correct 40 ms 7568 KB Output is correct
19 Correct 31 ms 6920 KB Output is correct
20 Correct 33 ms 7404 KB Output is correct
21 Correct 40 ms 8580 KB Output is correct
22 Correct 41 ms 8516 KB Output is correct
23 Correct 40 ms 8556 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Unexpected end of file - int64 expected
2 Halted 0 ms 0 KB -