Submission #670165

#	Time	Username	Problem	Language	Result	Execution time	Memory
670165		Cyanmond	Izvanzemaljci (COI21_izvanzemaljci)	C++17	26 / 100	131 ms	16212 KiB

izvanzemaljci

#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 = m; i < N; ++i) {
                C[i] = reverse_rotate(C[i].first, C[i].second);
            }
            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;
            }
            if (real_mid <= ok) {
                ok = mid;
                continue;
            }

            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;
    }
}

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