oj.uz

Submission #670170

# Submission time Handle Problem Language Result Execution time Memory
670170 2022-12-08T08:27:17 Z Cyanmond Izvanzemaljci (COI21_izvanzemaljci) C++17
68 / 100
 255 ms 524288 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, max_y1 - w1, max_x1, max_y1, w1);
            cp.points[1] = std::make_tuple(min_x2, max_y2 - w2, min_x2 + w2, max_y2, 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 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 75 ms 1876 KB Output is correct
8 Correct 80 ms 1876 KB Output is correct
9 Correct 76 ms 1860 KB Output is correct
10 Correct 75 ms 1748 KB Output is correct
11 Correct 75 ms 1876 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 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 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 130 ms 8220 KB Output is correct
11 Correct 127 ms 8132 KB Output is correct
12 Correct 127 ms 8136 KB Output is correct
13 Correct 128 ms 8136 KB Output is correct
14 Correct 129 ms 8136 KB Output is correct
15 Correct 132 ms 8128 KB Output is correct
16 Correct 131 ms 8128 KB Output is correct
17 Correct 115 ms 7452 KB Output is correct
18 Correct 112 ms 7220 KB Output is correct
19 Correct 104 ms 6576 KB Output is correct
20 Correct 108 ms 7028 KB Output is correct
21 Correct 125 ms 8064 KB Output is correct
22 Correct 126 ms 8044 KB Output is correct
23 Correct 128 ms 8208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 224 KB Output is correct
18 Correct 1 ms 296 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 300 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 0 ms 296 KB Output is correct
26 Correct 1 ms 212 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16112 KB Output is correct
2 Correct 74 ms 16116 KB Output is correct
3 Correct 67 ms 16180 KB Output is correct
4 Correct 66 ms 16112 KB Output is correct
5 Correct 72 ms 16084 KB Output is correct
6 Correct 65 ms 16100 KB Output is correct
7 Correct 66 ms 16100 KB Output is correct
8 Correct 65 ms 16104 KB Output is correct
9 Correct 62 ms 16136 KB Output is correct
10 Correct 69 ms 16116 KB Output is correct
11 Correct 65 ms 16084 KB Output is correct
12 Correct 66 ms 16104 KB Output is correct
13 Correct 50 ms 12904 KB Output is correct
14 Correct 56 ms 12912 KB Output is correct
15 Correct 52 ms 13032 KB Output is correct
16 Correct 55 ms 13036 KB Output is correct
17 Correct 52 ms 13188 KB Output is correct
18 Correct 55 ms 13168 KB Output is correct
19 Correct 51 ms 12476 KB Output is correct
20 Correct 50 ms 12468 KB Output is correct
21 Correct 55 ms 13456 KB Output is correct
22 Correct 62 ms 13484 KB Output is correct
23 Correct 46 ms 11496 KB Output is correct
24 Correct 46 ms 11516 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16084 KB Output is correct
2 Correct 69 ms 16096 KB Output is correct
3 Correct 74 ms 16152 KB Output is correct
4 Correct 69 ms 16084 KB Output is correct
5 Correct 72 ms 16136 KB Output is correct
6 Correct 68 ms 16128 KB Output is correct
7 Correct 68 ms 16144 KB Output is correct
8 Correct 68 ms 16124 KB Output is correct
9 Correct 69 ms 16120 KB Output is correct
10 Correct 75 ms 16212 KB Output is correct
11 Correct 68 ms 16116 KB Output is correct
12 Correct 70 ms 16160 KB Output is correct
13 Correct 68 ms 16140 KB Output is correct
14 Runtime error 255 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -