oj.uz

Submission #670165

# Submission time Handle Problem Language Result Execution time Memory
670165 2022-12-08T08:15:48 Z Cyanmond Izvanzemaljci (COI21_izvanzemaljci) C++17
26 / 100
 131 ms 16212 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 = 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 78 ms 2244 KB Output is correct
8 Correct 84 ms 2188 KB Output is correct
9 Correct 75 ms 2204 KB Output is correct
10 Correct 75 ms 2272 KB Output is correct
11 Correct 79 ms 2244 KB Output is correct

Subtask #2
21.0 / 21.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 1 ms 300 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 128 ms 8460 KB Output is correct
11 Correct 127 ms 8524 KB Output is correct
12 Correct 130 ms 8520 KB Output is correct
13 Correct 130 ms 8512 KB Output is correct
14 Correct 127 ms 8520 KB Output is correct
15 Correct 128 ms 8516 KB Output is correct
16 Correct 131 ms 8504 KB Output is correct
17 Correct 115 ms 7844 KB Output is correct
18 Correct 121 ms 7608 KB Output is correct
19 Correct 103 ms 6960 KB Output is correct
20 Correct 109 ms 7424 KB Output is correct
21 Correct 125 ms 8520 KB Output is correct
22 Correct 128 ms 8468 KB Output is correct
23 Correct 131 ms 8588 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 292 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 1 ms 300 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 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Incorrect 1 ms 212 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16172 KB Output is correct
2 Correct 69 ms 16148 KB Output is correct
3 Correct 69 ms 16128 KB Output is correct
4 Correct 68 ms 16100 KB Output is correct
5 Correct 68 ms 16144 KB Output is correct
6 Correct 69 ms 16172 KB Output is correct
7 Correct 65 ms 16128 KB Output is correct
8 Correct 75 ms 16132 KB Output is correct
9 Correct 68 ms 16128 KB Output is correct
10 Correct 65 ms 16128 KB Output is correct
11 Correct 67 ms 16140 KB Output is correct
12 Correct 70 ms 16136 KB Output is correct
13 Correct 51 ms 12888 KB Output is correct
14 Correct 51 ms 12896 KB Output is correct
15 Incorrect 52 ms 13020 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16104 KB Output is correct
2 Correct 70 ms 16140 KB Output is correct
3 Correct 67 ms 16092 KB Output is correct
4 Correct 65 ms 16140 KB Output is correct
5 Correct 66 ms 16124 KB Output is correct
6 Correct 65 ms 16112 KB Output is correct
7 Correct 69 ms 16212 KB Output is correct
8 Correct 66 ms 16108 KB Output is correct
9 Correct 66 ms 16108 KB Output is correct
10 Correct 66 ms 16140 KB Output is correct
11 Correct 66 ms 16084 KB Output is correct
12 Incorrect 65 ms 16112 KB Output isn't correct
13 Halted 0 ms 0 KB -