oj.uz

Submission #669985

# Submission time Handle Problem Language Result Execution time Memory
669985 2022-12-07T17:09:21 Z Cyanmond Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 167 ms 8716 KB 
#include <bits/stdc++.h>

using i64 = long long;

constexpr i64 inf = 1ll << 40;
constexpr i64 limit = 1000000000ll;

struct Answer {
    i64 width;
    std::array<std::tuple<i64, i64, 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, max_x, max_y, ans.width);
        ans.points[1] = std::make_tuple(-3 * limit, -3 * limit, -3 * limit + 1, -3 * limit + 1, 1);
        ans.points[2] = std::make_tuple(3 * limit - 1, 3 * limit - 1, 3 * limit, 3 * limit, 1);
        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];
            if (C[i - 1].first == C[i].first) {
                if (std::max(min_y1, min_y2) <= std::min(max_y1, max_y2)) {
                    continue;
                }
            }

            Answer cp;
            const i64 w1 = std::max({max_x1 - min_x1, max_y1 - min_y1, 1ll});
            const i64 w2 = std::max({max_x2 - min_x2, max_y2 - min_y2, 1ll});

            cp.points[0] = std::make_tuple(max_x1 - w1, min_y1, max_x1, min_y1 + w1, w1);
            cp.points[1] = std::make_tuple(min_x2, min_y2, min_x2 + w2, min_y2 + w2, w2);
            cp.width = std::max(w1, w2);

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

        ret.points[2] = std::make_tuple(-3 * limit, -3 * limit, -3 * limit + 1, -3 * limit + 1, 1);
        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 = [&](const i64 x, const i64 y) {
        return std::make_pair(y, -x);
    };

    auto reverse_rotate = [&](const i64 x, const i64 y) {
        return std::make_pair(-y, x);
    };

    auto rotate_all = [&]() {
        for (int i = 0; i < N; ++i) {
            std::tie(X[i], Y[i]) = rotate(X[i], Y[i]);
        }
    };

    auto reverse = [&](const i64 y) {
        return -y;
    };

    bool is_reversed = false;

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

    auto fix = [&](const Answer ans, const int rotate_count) {
        Answer res = ans;
        if (is_reversed) {
            for (int i = 0; i < K; ++i) {
                std::get<1>(res.points[i]) = reverse(std::get<1>(res.points[i]));
                std::get<3>(res.points[i]) = reverse(std::get<3>(res.points[i]));
            }
        }
        for (int c = 0; c < rotate_count; ++c) {
            for (int i = 0; i < K; ++i) {
                auto &[x1, y1, x2, y2, w] = res.points[i];
                std::tie(x1, y1) = reverse_rotate(x1, y1);
                std::tie(x2, y2) = reverse_rotate(x2, y2);
            }
        }

        for (int i = 0; i < K; ++i) {
            auto &[x1, y1, x2, y2, w] = res.points[i];
            x1 = std::min(x1, x2);
            y1 = std::min(y1, y2);
            x2 = w;
        }
        return res;
    };

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

    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 0 ms 256 KB Output is correct
3 Correct 0 ms 240 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 78 ms 1868 KB Output is correct
8 Correct 77 ms 1876 KB Output is correct
9 Correct 78 ms 1876 KB Output is correct
10 Correct 76 ms 1876 KB Output is correct
11 Correct 76 ms 1872 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 166 ms 8572 KB Output is correct
11 Correct 165 ms 8552 KB Output is correct
12 Correct 163 ms 8576 KB Output is correct
13 Correct 167 ms 8676 KB Output is correct
14 Correct 164 ms 8588 KB Output is correct
15 Correct 166 ms 8584 KB Output is correct
16 Correct 165 ms 8716 KB Output is correct
17 Correct 149 ms 7776 KB Output is correct
18 Correct 147 ms 7724 KB Output is correct
19 Correct 141 ms 6956 KB Output is correct
20 Correct 137 ms 7432 KB Output is correct
21 Correct 164 ms 8588 KB Output is correct
22 Correct 161 ms 8548 KB Output is correct
23 Correct 165 ms 8648 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 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 1 ms 212 KB Output is correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 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 340 KB Output isn't correct
2 Halted 0 ms 0 KB -