Submission #484459

#TimeUsernameProblemLanguageResultExecution timeMemory
484459valerikkHamburg Steak (JOI20_hamburg)C++17
21 / 100
3088 ms77500 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int INF = 1'000'000'000; const int N = 800005; struct Point { int x, y; }; struct Seg { int l, r; Seg() : l(1), r(N) {} Seg(int l, int r) : l(l), r(r) {} }; void self_intersect(Seg &a, const Seg &b) { a.l = max(a.l, b.l); a.r = min(a.r, b.r); } Seg intersect(Seg a, const Seg &b) { self_intersect(a, b); return a; } bool inside(int x, const Seg &s) { return x >= s.l && x <= s.r; } struct Rect { Seg x, y; Rect() : x{}, y{} {} Rect(const Seg &x, const Seg &y) : x(x), y(y) {} }; istream &operator>>(istream &stream, Rect &r) { stream >> r.x.l >> r.y.l >> r.x.r >> r.y.r; return stream; } void self_intersect(Rect &a, const Rect &b) { self_intersect(a.x, b.x); self_intersect(a.y, b.y); } Rect intersect(Rect a, const Rect &b) { self_intersect(a, b); return a; } bool inside(const Point &p, const Rect &r) { return inside(p.x, r.x) && inside(p.y, r.y); } int k; vector<int> vals; void adjust(int &val) { val = lower_bound(vals.begin(), vals.end(), val) - vals.begin(); } void output(const vector<Point> &pts) { for (const auto &[x, y] : pts) { cout << vals[x] << " " << vals[y] << "\n"; } exit(0); } vector<Rect> filter(vector<Rect> rects, Point p) { vector<Rect> res; for (auto r : rects) { if (!inside(p, r)) { res.push_back(r); } } return res; } void solve(const vector<Rect> &rects, const vector<Point> &pts) { if ((int)pts.size() == k) { if (rects.empty()) { output(pts); } return; } Rect intersection; for (const auto &rect : rects) { self_intersect(intersection, rect); } for (int x : {intersection.x.l, intersection.x.r}) { for (int y : {intersection.y.l, intersection.y.r}) { Point p = {x, y}; auto npts = pts; npts.push_back(p); vector<Rect> nrects; for (const auto &rect : rects) { if (!inside(p, rect)) { nrects.push_back(rect); } } solve(nrects, npts); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n >> k; vector<Rect> rects(n); for (auto &r : rects) { cin >> r; } vals.push_back(0); vals.push_back(INF + 1); for (const auto &r : rects) { vals.push_back(r.x.l); vals.push_back(r.x.r); vals.push_back(r.y.l); vals.push_back(r.y.r); } sort(vals.begin(), vals.end()); vals.erase(unique(vals.begin(), vals.end()), vals.end()); while (vals.size() <= N) { vals.back() = INF; vals.push_back(INF + 1); } for (auto &r : rects) { adjust(r.x.l); adjust(r.y.l); adjust(r.x.r); adjust(r.y.r); } solve(rects, vector<Point>{}); Rect intersection; for (const auto &r : rects) { self_intersect(intersection, r); } int dy = intersection.y.r, uy = intersection.y.l; int lx = intersection.x.r, rx = intersection.x.l; Seg base_sd = {lx + 1, rx - 1}, base_su = {lx + 1, rx - 1}; Seg base_sl = {dy + 1, uy - 1}, base_sr = {dy + 1, uy - 1}; vector<Seg> pref_dl(N + 1); vector<Seg> suff_dr(N + 1); vector<Seg> pref_du(N + 1); vector<Seg> suff_du(N + 1); vector<Seg> pref_lr(N + 1); vector<Seg> suff_lr(N + 1); vector<Seg> suff_lu(N + 1); vector<Seg> suff_ru(N + 1); for (const auto &r : rects) { int fd = inside(dy, r.y); int fu = inside(uy, r.y); int fl = inside(lx, r.x); int fr = inside(rx, r.x); if (fd + fu + fl + fr > 2) { continue; } if (fd + fu + fl + fr == 0) { assert(0); } if (fd + fu + fl + fr == 1) { if (fd) { self_intersect(base_sd, r.x); } else if (fu) { self_intersect(base_su, r.x); } else if (fl) { self_intersect(base_sl, r.y); } else { self_intersect(base_sr, r.y); } } else { if (fd && fu) { self_intersect(pref_du[r.x.r], r.x); self_intersect(suff_du[r.x.l], r.x); } else if (fd && fl) { self_intersect(pref_dl[r.x.r], r.y); } else if (fd && fr) { self_intersect(suff_dr[r.x.l], r.y); } else if (fl && fr) { self_intersect(pref_lr[r.y.r], r.y); self_intersect(suff_lr[r.y.l], r.y); } else if (fu && fl) { self_intersect(suff_lu[r.y.r], r.x); } else { self_intersect(suff_ru[r.y.r], r.x); } } } for (int i = 0; i < N; ++i) { self_intersect(pref_lr[i + 1], pref_lr[i]); self_intersect(pref_dl[i + 1], pref_dl[i]); self_intersect(pref_du[i + 1], pref_du[i]); } for (int i = N; i > 0; --i) { self_intersect(suff_dr[i - 1], suff_dr[i]); self_intersect(suff_du[i - 1], suff_du[i]); self_intersect(suff_lu[i - 1], suff_lu[i]); self_intersect(suff_ru[i - 1], suff_ru[i]); self_intersect(suff_lr[i - 1], suff_lr[i]); } for (int dx = base_sd.l; dx <= base_sd.r; ++dx) { solve(filter(rects, Point{dx, dy}), vector<Point>{Point{dx, dy}}); Seg su = base_su, sl = base_sl, sr = base_sr; self_intersect(sl, pref_dl[dx - 1]); self_intersect(sr, suff_dr[dx + 1]); self_intersect(su, pref_du[dx - 1]); self_intersect(su, suff_du[dx + 1]); int ly = intersect(sl, pref_lr[N]).r; if (!inside(ly, sl)) { continue; } self_intersect(sr, pref_lr[ly - 1]); self_intersect(sr, suff_lr[ly + 1]); if (sr.l > sr.r) { continue; } int ry = sr.r; self_intersect(su, suff_lu[ly + 1]); self_intersect(su, suff_ru[ry + 1]); if (su.l > su.r) { continue; } int ux = su.l; output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}}); } for (int dx = base_sd.l; dx <= base_sd.r; ++dx) { Seg su = base_su, sl = base_sl, sr = base_sr; self_intersect(sl, pref_dl[dx - 1]); self_intersect(sr, suff_dr[dx + 1]); self_intersect(su, pref_du[dx - 1]); self_intersect(su, suff_du[dx + 1]); int ry = intersect(sr, pref_lr[N]).r; if (!inside(ry, sr)) { continue; } self_intersect(sl, pref_lr[ry - 1]); self_intersect(sl, suff_lr[ry + 1]); if (sl.l > sl.r) { continue; } int ly = sl.r; self_intersect(su, suff_lu[ly + 1]); self_intersect(su, suff_ru[ry + 1]); if (su.l > su.r) { continue; } int ux = su.l; output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}}); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...