Submission #386587

#	Time	Username	Problem	Language	Result	Execution time	Memory
386587		timmyfeng	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	888 ms	14616 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

const int N = 200000, X = 1000000000;

vector<array<int, 2>> skewers;
array<int, 4> rects[N];
bool tested[N];
int n;

array<int, 4> bounds() {
    int x1 = X, x2 = 1, y1 = X, y2 = 1;
    for (int i = 0; i < n; ++i) {
        if (!tested[i]) {
            auto [x3, x4, y3, y4] = rects[i];
            x1 = min(x1, x4);
            x2 = max(x2, x3);
            y1 = min(y1, y4);
            y2 = max(y2, y3);
        }
    }
    return {x1, x2, y1, y2};
}

void print() {
    for (auto [x, y] : skewers) {
        cout << x << " " << y << "\n";
    }
    exit(0);
}

void solve(int k) {
    if (k == 0) {
        if (count(tested, tested + n, true) == n) {
            print();
        }
        return;
    }

    auto [x1, x2, y1, y2] = bounds();

    for (auto x : {x1, x2}) {
        for (auto y : {y1, y2}) {
            skewers.push_back({x, y});
            vector<int> undo;
            for (int i = 0; i < n; ++i) {
                if (!tested[i]) {
                    auto [x3, x4, y3, y4] = rects[i];
                    if (x3 <= x && x <= x4 && y3 <= y && y <= y4) {
                        tested[i] = true;
                        undo.push_back(i);
                    }
                }
            }

            solve(k - 1);

            for (auto i : undo) {
                tested[i] = false;
            }
            skewers.pop_back();
        }
    }
}

void build(vector<array<int, 2>> &points) {
    sort(rbegin(points), rend(points));
    vector<array<int, 2>> hull;
    for (auto [x, y] : points) {
        if (hull.empty() || hull.back()[1] > y) {
            hull.push_back({x, y});
        }
    }
    reverse(begin(hull), end(hull));
    points = hull;
}

int query(vector<array<int, 2>> &hull, int x) {
    auto it = upper_bound(begin(hull), end(hull), array<int, 2>{x, X});
    return it == end(hull) ? X : it->at(1);
}

void solve_4() {
    auto [x1, x2, y1, y2] = bounds();

    int l1 = y1, r1 = y1, l2 = y2, r2 = y2, d1 = x1, u1 = x1, d2 = x2, u2 = x2;
    vector<array<int, 2>> ld, lu, dr, ur, du, lrud, lruu, lrdd, lrdu;

    for (int i = 0; i < n; ++i) {
        auto [x3, x4, y3, y4] = rects[i];
        bool l = x3 <= x1, r = x4 >= x2, d = y3 <= y1, u = y4 >= y2;
        if (l + r + d + u <= 2) {
            if (l && r) {
                lrud.push_back({y3, -y3});
                lruu.push_back({y3, y4});
                lrdd.push_back({-y4, -y3});
                lrdu.push_back({-y4, y4});
            } else if (d && u) {
                du.push_back({x3, x4});
                u1 = max(u1, x3);
                d2 = min(d2, x4);
            } else if (l && d) {
                ld.push_back({-y4, x4});
            } else if (l && u) {
                lu.push_back({y3, x4});
            } else if (d && r) {
                dr.push_back({x3, y4});
            } else if (u && r) {
                ur.push_back({x3, -y3});
            } else if (l) {
                l1 = max(l1, y3);
                l2 = min(l2, y4);
            } else if (r) {
                r1 = max(r1, y3);
                r2 = min(r2, y4);
            } else if (d) {
                d1 = max(d1, x3);
                d2 = min(d2, x4);
            } else if (u) {
                u1 = max(u1, x3);
                u2 = min(u2, x4);
            }
        }
    }

    build(ld), build(lu), build(dr), build(ur), build(du);
    build(lrud), build(lruu), build(lrdd), build(lrdu);

    for (int i = 0; i < n; ++i) {
        for (auto l : rects[i]) {
            if (l1 <= l && l <= l2) {
                int d = min({d2, query(ld, -l)});
                if (d1 <= d) {
                    int u = min({u2, query(lu, l), query(du, d)});
                    if (u1 <= u) {
                        int r3 = max({r1, -query(ur, u), -query(lrud, l), -query(lrdd, -l)});
                        int r4 = min({r2, query(dr, d), query(lruu, l), query(lrdu, -l)});
                        if (r3 <= r4) {
                            skewers = {{x1, l}, {x2, r3}, {d, y1}, {u, y2}};
                            return;
                        }
                    }
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int k;
    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> rects[i][0] >> rects[i][2] >> rects[i][1] >> rects[i][3];
    }

    solve(k);

    solve_4();

    if (!skewers.empty()) {
        print();
    }

    for (int i = 0; i < n; ++i) {
        auto &[x1, x2, y1, y2] = rects[i];
        y1 = X + 1 - y1;
        y2 = X + 1 - y2;
        swap(y1, y2);
    }

    solve_4();

    for (auto &[x, y] : skewers) {
        y = X + 1 - y;
    }

    print();
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79