답안 #670159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670159 2022-12-08T08:01:30 Z Cyanmond Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
136 ms 16120 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 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 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_k2sub = [](int N, std::vector<std::pair<i64, i64>> C) {
        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);
        }

        return ret;
    };

    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());

        auto ret = solve_k2sub(N, C);
        ret.points[2] = std::make_tuple(-3 * limit, -3 * limit, -3 * limit + 1, -3 * limit + 1, 1);
        return ret;
    };

    auto solve_k3_sub1 = [&]() {
        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_l[0] = -inf;
        min_y_l[0] = inf;
        for (int i = 0; i < N; ++i) {
            max_y_l[i + 1] = min_y_l[i + 1] = 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]);
        }

        auto calc = [&](int m) -> std::pair<Answer, Answer> {
            const i64 max_x = C[m - 1].first, min_x = C[0].first;
            const i64 max_y = max_y_l[m], min_y = min_y_l[m];
            const i64 w = std::max(max_x - min_x, max_y - min_y);

            Answer res1;
            res1.width = w;
            res1.points[0] = std::make_tuple(max_x - w, min_y, max_x, min_y + w, w);

            for (int i = m; i < N; ++i) {
                C[i] = rotate(C[i].first, C[i].second);
            }
            auto res2 = solve_k2sub(N - m, std::vector(C.begin() + m, C.end()));
            for (int i = 0; i < K; ++i) {
                auto &[x1, y1, x2, y2, w] = res2.points[i];
                std::tie(x1, y1) = reverse_rotate(x1, y1);
                std::tie(x2, y2) = reverse_rotate(x2, y2);
            }
            return std::make_pair(res1, res2);
        };

        int ok = 0, ng = N;
        Answer ans;
        ans.width = inf;
        while (std::abs(ok - ng) > 1) {
            const auto mid = (ok + ng) / 2;
            int real_mid = mid;
            while (real_mid != 0 and C[real_mid - 1].first == C[real_mid].first) {
                --real_mid;
            }

            auto [res1, res2] = calc(real_mid);
            if (res1.width < res2.width) {
                ok = mid;
            } else {
                ng = mid;
            }

            res2.width = std::max(res1.width, res2.width);
            res2.points[2] = res1.points[0];
            ans = std::min(ans, res2);
        }

        return ans;
    };

    auto solve_k3_sub2 = [&]() {
        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());
        
        struct cord {
            i64 x;
            i64 y_max;
            i64 y_min;
        };
        std::vector<cord> D;
        D.push_back({C[0].first, C[0].second, C[0].second});
        for (int i = 1; i < N; ++i) {
            if (C[i].first == C[i - 1].first) {
                D.back().y_max = std::max(D.back().y_max, C[i].second);
                D.back().y_min = std::min(D.back().y_min, C[i].second);
            } else {
                D.push_back({C[i].first, C[i].second, C[i].second});
            }
        }
        const int M = (int)D.size();

        std::vector<std::vector<i64>> y_max(M, std::vector<i64>(M, -inf)), y_min(M, std::vector<i64>(M, inf));
        for (int l = 0; l < M; ++l) {
            i64 y_ma = D[l].y_max, y_mi = D[l].y_min;
            for (int r = l; r < M; ++r) {
                y_ma = std::max(y_ma, D[r].y_max);
                y_mi = std::min(y_mi, D[r].y_min);
                y_max[l][r] = y_ma;
                y_min[l][r] = y_mi;
            }
        }

        Answer ret;
        ret.width = inf;
        for (int i = 1; i < M; ++i) {
            for (int j = i + 1; j < M; ++j) {
                Answer res;
                const i64 x_ma_1 = D[i - 1].x, x_mi_1 = D[0].x;
                const i64 x_ma_2 = D[j - 1].x, x_mi_2 = D[i].x;
                const i64 x_ma_3 = D[M - 1].x, x_mi_3 = D[j].x;
                const i64 y_ma_1 = y_max[0][i - 1], y_mi_1 = y_min[0][i - 1];
                const i64 y_ma_2 = y_max[i][j - 1], y_mi_2 = y_min[i][j - 1];
                const i64 y_ma_3 = y_max[j][M - 1], y_mi_3 = y_min[j][M - 1];

                const i64 w1 = std::max({x_ma_1 - x_mi_1, y_ma_1 - y_mi_1, 1ll});
                const i64 w2 = std::max({x_ma_2 - x_mi_2, y_ma_2 - y_mi_2, 1ll});
                const i64 w3 = std::max({x_ma_3 - x_mi_3, y_ma_3 - y_mi_3, 1ll});
                const i64 width = std::max({w1, w2, w3});

                if (w2 > x_mi_3 - x_ma_1 - 2) {
                    continue;
                }

                res.width = width;
                if (res.width < ret.width) {
                    res.points[0] = std::make_tuple(x_ma_1 - w1, y_mi_1, x_ma_1, y_mi_1 + w1, w1);
                    res.points[2] = std::make_tuple(x_mi_3, y_mi_3, x_ma_3 + w3, y_mi_3 + w3, w3);
                    i64 xmi2 = x_ma_1 + 1;
                    if (xmi2 + w2 < x_ma_2) {
                        xmi2 = x_ma_2 - w2;
                    }
                    res.points[1] = std::make_tuple(xmi2, y_mi_2, xmi2 + w2, y_mi_2 + w2, w2);
                    ret = res;
                }
            }
        }

        return ret;
    };

    auto solve_k3 = [&]() -> Answer {
        return std::min(solve_k3_sub1(), solve_k3_sub2());
    };

    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_all = [&]() {
        for (int i = 0; i < N; ++i) {
            std::tie(X[i], Y[i]) = rotate(X[i], Y[i]);
        }
    };

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

    bool is_reversed = false;

    auto reverse_all = [&]() {
        for (int i = 0; i < N; ++i) {
            X[i] = reverse(X[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<0>(res.points[i]) = reverse(std::get<0>(res.points[i]));
                std::get<2>(res.points[i]) = reverse(std::get<2>(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 < 2; ++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;
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 76 ms 3888 KB Output is correct
8 Correct 77 ms 3772 KB Output is correct
9 Correct 78 ms 3888 KB Output is correct
10 Correct 78 ms 3892 KB Output is correct
11 Correct 77 ms 3788 KB Output is correct
# 결과 실행 시간 메모리 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 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 136 ms 10196 KB Output is correct
11 Correct 130 ms 10164 KB Output is correct
12 Correct 133 ms 10156 KB Output is correct
13 Correct 131 ms 10080 KB Output is correct
14 Correct 132 ms 10160 KB Output is correct
15 Correct 130 ms 10168 KB Output is correct
16 Correct 133 ms 10056 KB Output is correct
17 Correct 118 ms 9288 KB Output is correct
18 Correct 114 ms 8980 KB Output is correct
19 Correct 103 ms 8196 KB Output is correct
20 Correct 111 ms 8780 KB Output is correct
21 Correct 128 ms 10152 KB Output is correct
22 Correct 127 ms 10068 KB Output is correct
23 Correct 130 ms 10108 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 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 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 16120 KB Output isn't correct
2 Halted 0 ms 0 KB -