oj.uz

Submission #669889

# Submission time Handle Problem Language Result Execution time Memory
669889 2022-12-07T15:23:00 Z Cyanmond Izvanzemaljci (COI21_izvanzemaljci) C++17
5 / 100
 86 ms 3788 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1ll << 40;

struct Answer {
    i64 width;
    std::array<std::tuple<i64, i64, i64>, 3> points;
};

bool operator <(const Answer &a, const Answer &b) {
    return a.width < b.width;
}

int main() {
    int N, K;
    std::cin >> N >> K;
    std::vector<i64> X(N), Y(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> X[i] >> Y[i];
    }

    auto solve_k1 = [&]() -> Answer {
        const i64 max_x = *std::max_element(X.begin(), X.end());
        const i64 min_x = *std::min_element(X.begin(), X.end());
        const i64 max_y = *std::max_element(Y.begin(), Y.end());
        const i64 min_y = *std::min_element(Y.begin(), Y.end());

        Answer ans;
        ans.width = std::max(max_x - min_x, max_y - min_y);
        ans.points[0] = std::make_tuple(min_x, min_y, ans.width);
        return ans;
    };

    auto solve_k2 = [&]() -> Answer {
        std::vector<std::pair<i64, i64>> C(N);
        for (int i = 0; i < N; ++i) {
            C[i] = {X[i], Y[i]};
        }
        std::sort(C.begin(), C.end());

        std::vector<i64> max_y_l(N + 1), min_y_l(N + 1), max_y_r(N + 1), min_y_r(N + 1);
        max_y_l[0] = max_y_r[N] = -inf;
        min_y_l[0] = min_y_r[N] = inf;
        for (int i = 0; i < N; ++i) {
            max_y_l[i + 1] = min_y_l[i + 1] = C[i].second;
            max_y_r[i] = min_y_r[i] = C[i].second;
        }
        for (int i = 0; i < N; ++i) {
            max_y_l[i + 1] = std::max(max_y_l[i + 1], max_y_l[i]);
            min_y_l[i + 1] = std::min(min_y_l[i + 1], min_y_l[i]);
        }
        for (int i = N; i > 0; --i) {
            max_y_r[i - 1] = std::max(max_y_r[i - 1], max_y_r[i]);
            min_y_r[i - 1] = std::min(min_y_r[i - 1], min_y_r[i]);
        }

        Answer ret;
        ret.width = inf;
        for (int i = 1; i < N; ++i) {
            const i64 max_x1 = C[i - 1].first, min_x1 = C[0].first;
            const i64 max_x2 = C[N - 1].first, min_x2 = C[i].first;
            const i64 max_y1 = max_y_l[i], min_y1 = min_y_l[i];
            const i64 max_y2 = max_y_r[i], min_y2 = min_y_r[i];

            Answer cp;
            const i64 w1 = std::max(max_x1 - min_x1, max_y1 - min_y1);
            const i64 w2 = std::max(max_x2 - min_x2, max_y2 - min_y2);
            cp.points[0] = std::make_tuple(max_x1 - w1, min_y1, w1);
            cp.points[1] = std::make_tuple(min_x2, min_y2, w2);
            cp.width = std::max(w1, w2);

            ret = std::min(ret, cp);
        }

        return ret;
    };

    auto solve_k3 = [&]() -> Answer {
        Answer ret;
        return ret;
    };

    auto solve = [&]() {
        if (K == 1) {
            return solve_k1();
        } else if (K == 2) {
            return std::min(solve_k1(), solve_k2());
        } else {
            return std::min({solve_k1(), solve_k2(), solve_k3()});
        }
    };

    auto rotate = [&]() {
        for (int i = 0; i < N; ++i) {
            const auto new_x = Y[i], new_y = -X[i];
            X[i] = new_x;
            Y[i] = new_y;
        }
    };

    auto reverse = [&]() {
        for (int i = 0; i < N; ++i) {
            Y[i] = 0 - Y[i];
        }
    };

    Answer answer;
    answer.width = inf;
    for (int i = 0; i < 4; ++i) {
        answer = std::min(answer, solve());
        reverse();
        answer = std::min(answer, solve());
        reverse();
        rotate();
    }

    for (int i = 0; i < K; ++i) {
        std::cout << std::get<0>(answer.points[i]) << ' ';
        std::cout << std::get<1>(answer.points[i]) << ' ';
        std::cout << std::max(1ll, std::get<2>(answer.points[i])) << std::endl;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 77 ms 3776 KB Output is correct
8 Correct 86 ms 3788 KB Output is correct
9 Correct 80 ms 3788 KB Output is correct
10 Correct 80 ms 3788 KB Output is correct
11 Correct 80 ms 3788 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 300 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 0 ms 300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -