Submission #216313

#	Time	Username	Problem	Language	Result	Execution time	Memory
216313		model_code	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	1087 ms	32700 KiB

hamburg

#include <iostream>
#include <vector>
#include <array>
#include <tuple>
#include <algorithm>
#include <cassert>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
constexpr ll TEN(int n) { return (n == 0 ? 1 : 10 * TEN(n - 1)); }
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;

const int INF = TEN(9) + TEN(8);

struct P {
    int x, y;
    bool operator<(P r) const {
        return tie(x, y) < tie(r.x, r.y);
    }

};

struct Rect {
    P ld, ru;
    bool inside(P p) const {
        return (ld.x <= p.x && p.x <= ru.x)
            && (ld.y <= p.y && p.y <= ru.y);
    }
};

V<Rect> filter(const V<Rect>& rects, P p) {
    V<Rect> v;
    for (auto rect: rects) {
        if (rect.inside(p)) continue;
        v.push_back(rect);
    }
    return v;
}

V<P> join(V<P> a, const V<P>& b) {
    for (auto p: b) a.push_back(p);
    return a;
}

bool inside(int a, int b, int c) { return b <= a && a <= c; }

struct SuperVector {
    V<P> ps;
    V<int> l_mi, l_ma, r_mi, r_ma;
    void init() {
        sort(ps.begin(), ps.end(), [&](P l, P r) {
            return l.x < r.x;
        });
        int n = int(ps.size());
        l_mi = l_ma = V<int>(n + 1);
        l_mi[0] = INF;
        l_ma[0] = -INF;
        for (int i = 0; i < n; i++) {
            l_mi[i + 1] = min(l_mi[i], ps[i].y);
            l_ma[i + 1] = max(l_ma[i], ps[i].y);
        }
        r_mi = r_ma = V<int>(n + 1);
        r_mi[n] = INF;
        r_ma[n] = -INF;
        for (int i = n - 1; i >= 0; i--) {
            r_mi[i] = min(r_mi[i + 1], ps[i].y);
            r_ma[i] = max(r_ma[i + 1], ps[i].y);
        }
    }

    int l_min(int x) {
        int idx = int(lower_bound(ps.begin(), ps.end(), P{x, -INF}) - ps.begin());
        return l_mi[idx];
    }
    int l_max(int x) {
        int idx = int(lower_bound(ps.begin(), ps.end(), P{x, -INF}) - ps.begin());
        return l_ma[idx];
    }

    int r_min(int x) {
        int idx = int(lower_bound(ps.begin(), ps.end(), P{x, INF}) - ps.begin());
        return r_mi[idx];
    }
    int r_max(int x) {
        int idx = int(lower_bound(ps.begin(), ps.end(), P{x, INF}) - ps.begin());
        return r_ma[idx];
    }
};

V<P> solve4_cross(V<Rect> rects) {
    int l = INF, d = INF, r = -INF, u = -INF;
    for (auto rect : rects) {
        l = min(l, rect.ru.x);
        d = min(d, rect.ru.y);
        r = max(r, rect.ld.x);
        u = max(u, rect.ld.y);
    }

    int l_min = d, l_max = u;
    int d_min = l, d_max = r;
    int r_min = d, r_max = u;
    int u_min = l, u_max = r;

    SuperVector lu, ur, rd, dl, lr, ud;
    for (auto rect : rects) {
        if (l < rect.ld.x && rect.ru.x < r) {
            if (d < rect.ld.y) {
                u_min = max(u_min, rect.ld.x);
                u_max = min(u_max, rect.ru.x);
                continue;
            }
            if (rect.ru.y < u) {
                d_min = max(d_min, rect.ld.x);
                d_max = min(d_max, rect.ru.x);
                continue;
            }
            u_max = min(u_max, rect.ru.x);
            d_min = max(d_min, rect.ld.x);
            ud.ps.push_back({rect.ld.x, rect.ru.x});
            continue;
        }
        if (d < rect.ld.y && rect.ru.y < u) {
            if (l < rect.ld.x) {
                r_min = max(r_min, rect.ld.y);
                r_max = min(r_max, rect.ru.y);
                continue;
            }
            if (rect.ru.x < r) {
                l_min = max(l_min, rect.ld.y);
                l_max = min(l_max, rect.ru.y);
                continue;
            }
            l_max = min(l_max, rect.ru.y);
            r_min = max(r_min, rect.ld.y);
            lr.ps.push_back({rect.ld.y, rect.ru.y});
            continue;
        }
        if (rect.ru.x < r && rect.ru.y < u) {
            dl.ps.push_back({rect.ru.x, rect.ru.y});
            continue;
        }
        if (rect.ru.x < r && d < rect.ld.y) {
            lu.ps.push_back({rect.ld.y, rect.ru.x});
            continue;
        }
        if (l < rect.ld.x && d < rect.ld.y) {
            ur.ps.push_back({rect.ld.x, rect.ld.y});
            continue;
        }
        if (l < rect.ld.x && rect.ru.y < u) {
            rd.ps.push_back({rect.ru.y, rect.ld.x});
            continue;
        }
    }
    lu.init(); ur.init(); rd.init(); dl.init(); lr.init(); ud.init();

    V<int> l_pred = {l_min, l_max};
    for (auto rect: rects) {
        l_pred.push_back(rect.ld.y);
        l_pred.push_back(rect.ru.y);
    }

    for (int _l : l_pred) {
        if (!inside(_l, l_min, l_max)) continue;
        int _u = min(u_max, lu.r_min(_l));
        if (_u < u_min) continue;
        int _r = max(r_min, ur.r_max(_u));
        if (min(lr.r_min(_l), r_max) < _r) continue;
        int _d = max(d_min, rd.l_max(_r));
        if (min(ud.r_min(_u), d_max) < _d) continue;
        if (dl.l_min(_d) < _l) continue;

        return {
            P{l, _l},
            P{_u, u},
            P{r, _r},
            P{_d, d},
        };
    }

    return {};
}

V<P> solve4_non_cross(V<Rect> rects) {
    int l = INF, d = INF, r = -INF, u = -INF;
    for (auto rect : rects) {
        l = min(l, rect.ru.x);
        d = min(d, rect.ru.y);
        r = max(r, rect.ld.x);
        u = max(u, rect.ld.y);
    }

    int l_min = d, l_max = u;
    int d_min = l, d_max = r;
    int r_min = d, r_max = u;
    int u_min = l, u_max = r;

    SuperVector ld, lu, du, dr, ur, lr;
    for (auto rect : rects) {
        if (l < rect.ld.x && rect.ru.x < r) {
            if (d < rect.ld.y) {
                u_min = max(u_min, rect.ld.x);
                u_max = min(u_max, rect.ru.x);
                continue;
            }
            if (rect.ru.y < u) {
                d_min = max(d_min, rect.ld.x);
                d_max = min(d_max, rect.ru.x);
                continue;
            }
            d_max = min(d_max, rect.ru.x);
            u_min = max(u_min, rect.ld.x);
            du.ps.push_back({rect.ld.x, rect.ru.x});
            continue;
        }
        if (d < rect.ld.y && rect.ru.y < u) {
            if (l < rect.ld.x) {
                r_min = max(r_min, rect.ld.y);
                r_max = min(r_max, rect.ru.y);
                continue;
            }
            if (rect.ru.x < r) {
                l_min = max(l_min, rect.ld.y);
                l_max = min(l_max, rect.ru.y);
                continue;
            }
            l_max = min(l_max, rect.ru.y);
            r_min = max(r_min, rect.ld.y);
            lr.ps.push_back({rect.ld.y, rect.ru.y});
            continue;
        }
        if (rect.ru.x < r && rect.ru.y < u) {
            ld.ps.push_back({rect.ru.y, rect.ru.x});
            continue;
        }
        if (rect.ru.x < r && d < rect.ld.y) {
            lu.ps.push_back({rect.ld.y, rect.ru.x});
            continue;
        }
        if (l < rect.ld.x && d < rect.ld.y) {
            ur.ps.push_back({rect.ld.x, rect.ld.y});
            continue;
        }
        if (l < rect.ld.x && rect.ru.y < u) {
            dr.ps.push_back({rect.ld.x, rect.ru.y});
            continue;
        }
    }
    ld.init(); lu.init(); du.init(); dr.init(); ur.init(); lr.init();

    V<int> l_pred = {l_min, l_max};
    for (auto rect : rects) {
        l_pred.push_back(rect.ld.y);
        l_pred.push_back(rect.ru.y);
    }

    for (int _l : l_pred) {
        if (!inside(_l, l_min, l_max)) continue;
        int _d = min(d_max, ld.l_min(_l)); 
        if (_d < d_min) continue;
        int _u = min({u_max, lu.r_min(_l), du.r_min(_d)});
        if (_u < u_min) continue;        
        int _r = min({r_max, dr.r_min(_d), lr.r_min(_l)});
        if (_r < max(r_min, ur.r_max(_u))) continue;
        return {
            P{l, _l},
            P{_u, u},
            P{r, _r},
            P{_d, d},
        };
    }

    return {};
}

V<P> solve(V<Rect> rects, int K) {
    assert(1 <= K && K <= 4);
    if (rects.empty()) return V<P>(K, P{1, 1});
    int l = INF, d = INF, r = -INF, u = -INF;
    for (auto rect : rects) {
        l = min(l, rect.ru.x);
        d = min(d, rect.ru.y);
        r = max(r, rect.ld.x);
        u = max(u, rect.ld.y);
    }
    for (auto x: {l, r}) {
        for (auto y: {d, u}) {
            P p = {x, y};
            auto nrects = filter(rects, p);
            if (K == 1) {
                if (nrects.empty()) return {p};
            } else {
                auto ans = solve(nrects, K - 1);
                if (!ans.empty()) return join(ans, {p});
            }
        }
    }

    if (K <= 3) return {};
    assert(K == 4);
    for (int ph = 0; ph < 2; ph++) {
        auto ans = solve4_cross(rects);
        if (!ans.empty()) {
            if (ph) {
                for (auto& p : ans) {
                    p.x *= -1;
                }
            }
            return ans;
        }
        for (auto& rect: rects) {
            swap(rect.ld.x, rect.ru.x);
            rect.ld.x *= -1;
            rect.ru.x *= -1;
        }
    }

    for (int ph = 0; ph < 2; ph++) {
        auto ans = solve4_non_cross(rects);
        if (!ans.empty()) {
            if (ph) {
                for (auto& p : ans) {
                    p.x *= -1;
                }
            }
            return ans;
        }
        for (auto& rect : rects) {
            swap(rect.ld.x, rect.ru.x);
            rect.ld.x *= -1;
            rect.ru.x *= -1;
        }
    }
    return {};
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    V<Rect> rects(n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d %d", &rects[i].ld.x, &rects[i].ld.y, &rects[i].ru.x, &rects[i].ru.y);
    }

    auto ans = solve(rects, k);

    assert(!ans.empty());
    for (auto p: ans) {
        printf("%d %d\n", p.x, p.y);
    }
    return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:342:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  342 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:345:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  345 |         scanf("%d %d %d %d", &rects[i].ld.x, &rects[i].ld.y, &rects[i].ru.x, &rects[i].ru.y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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