Submission #223861

#TimeUsernameProblemLanguageResultExecution timeMemory
223861MinnakhmetovHamburg Steak (JOI20_hamburg)C++14
15 / 100
386 ms25632 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(aaa) aaa.begin(), aaa.end() const int N = 4e5 + 5, INF = 1e9 + 5; struct R { int xl, yl, xr, yr; bool contains(int x, int y) const { return x >= xl && x <= xr && y >= yl && y <= yr; } bool intersects_hor(int y) const { return y >= yl && y <= yr; } bool intersects_ver(int x) const { return x >= xl && x <= xr; } }; vector<R> rcs; vector<int> vx, vy; vector<pair<int, int>> ans; pair<int, int> suf_hor[N], pref_ver[N], suf_ver[N]; int pref[N], suf[N], suf_lt[N], suf_rt[N]; pair<int, int> intersection(pair<int, int> a, pair<int, int> b) { return {max(a.first, b.first), min(a.second, b.second)}; } bool solve_for_line(vector<pair<int, int>> v, int k, bool hor, int x) { sort(all(v)); int last = N; vector<int> w; for (int i = (int)v.size() - 1; i >= 0; i--) { if (v[i].second < last) { if (k == 0) return false; k--; last = v[i].first; w.push_back(last); } } for (int y : w) { ans.push_back(hor ? make_pair(y, x) : make_pair(x, y)); } return true; } vector<R> remove_covered(vector<R> v, int x, int y) { vector<R> nv; for (const R &rc : v) { if (!rc.contains(x, y)) { nv.push_back(rc); } } return nv; } bool solve(vector<R> v, int k) { int mn_xr = N, mx_xl = -1, mn_yr = N, mx_yl = -1; for (R &rc : v) { mn_xr = min(mn_xr, rc.xr); mn_yr = min(mn_yr, rc.yr); mx_xl = max(mx_xl, rc.xl); mx_yl = max(mx_yl, rc.yl); } if (mn_xr >= mx_xl && mn_yr >= mx_yl) { ans.push_back({mn_xr, mn_yr}); return true; } else if (mn_xr >= mx_xl) { vector<pair<int, int>> sgs; for (R &rc : v) { sgs.push_back({rc.yl, rc.yr}); } if (solve_for_line(sgs, k, false, mn_xr)) return true; return false; } else if (mn_yr >= mx_yl) { vector<pair<int, int>> sgs; for (R &rc : v) { sgs.push_back({rc.xl, rc.xr}); } if (solve_for_line(sgs, k, true, mn_yr)) return true; return false; } else if (k == 2) { for (int y : {mn_yr, mx_yl}) { if (solve(remove_covered(v, mn_xr, y), k - 1)) { ans.push_back({mn_xr, y}); return true; } } return false; } else if (k >= 2) { for (int x : {mn_xr, mx_xl}) { for (int y : {mn_yr, mx_yl}) { if (solve(remove_covered(v, x, y), k - 1)) { ans.push_back({x, y}); return true; } } } if (k == 3) return false; pair<int, int> up, rt, lt, dn; dn = up = {1, vx.size() - 2}; lt = rt = {1, vy.size() - 2}; fill(suf_hor, suf_hor + N, make_pair(1, vy.size() - 2)); fill(pref_ver, pref_ver + N, make_pair(1, vx.size() - 2)); fill(suf_ver, suf_ver + N, make_pair(1, vx.size() - 2)); fill(pref, pref + N, vy.size() - 2); fill(suf, suf + N, vy.size() - 2); fill(suf_lt, suf_lt + N, vx.size() - 2); fill(suf_rt, suf_rt + N, 1); for (const R &rc : v) { bool d = rc.intersects_hor(mn_yr), u = rc.intersects_hor(mx_yl), l = rc.intersects_ver(mn_xr), r = rc.intersects_ver(mx_xl); int ct = d + u + l + r; if (ct == 1) { if (l) lt = intersection(lt, {rc.yl, rc.yr}); else if (r) rt = intersection(rt, {rc.yl, rc.yr}); else if (u) up = intersection(up, {rc.xl, rc.xr}); else dn = intersection(dn, {rc.xl, rc.xr}); } else if (ct == 2) { if (l && r) { suf_hor[rc.yl] = intersection(suf_hor[rc.yl], make_pair(rc.yl, rc.yr)); } else if (d && l) { pref[rc.xr] = min(pref[rc.xr], rc.yr); } else if (d && r) { suf[rc.xl] = min(suf[rc.xl], rc.yr); } else if (l && u) { suf_lt[rc.yl] = min(rc.xr, suf_lt[rc.yl]); } else if (r && u) { suf_rt[rc.yl] = max(rc.xl, suf_rt[rc.yl]); } else { pref_ver[rc.xr] = intersection(pref_ver[rc.xr], {rc.xl, rc.xr}); suf_ver[rc.xl] = intersection(suf_ver[rc.xl], {rc.xl, rc.xr}); } } } for (int i = N - 2; i >= 0; i--) { suf_hor[i] = intersection(suf_hor[i], suf_hor[i + 1]); suf_lt[i] = min(suf_lt[i], suf_lt[i + 1]); suf_rt[i] = max(suf_rt[i], suf_rt[i + 1]); suf_ver[i] = intersection(suf_ver[i], suf_ver[i + 1]); suf[i] = min(suf[i], suf[i + 1]); } for (int i = 1; i < N; i++) { pref_ver[i] = intersection(pref_ver[i], pref_ver[i - 1]); pref[i] = min(pref[i], pref[i - 1]); } for (int i = dn.first; i <= dn.second; i++) { int mx_lt = pref[i - 1], mx_rt = suf[i + 1]; pair<int, int> nup = intersection(up, intersection(pref_ver[i - 1], suf_ver[i + 1])); if (nup.first > nup.second) { continue; } int y_lt = min(mx_lt, suf_hor[0].second); y_lt = min(y_lt, lt.second); if (y_lt < lt.first) { continue; } pair<int, int> nrt = intersection(rt, suf_hor[y_lt + 1]); if (nrt.first > nrt.second) { continue; } int y_rt = nrt.second; nup = intersection(nup, make_pair(suf_rt[y_rt + 1], suf_lt[y_lt + 1])); if (nup.first > nup.second) { continue; } ans.push_back({i, mn_yr}); ans.push_back({mn_xr, y_lt}); ans.push_back({mx_xl, y_rt}); ans.push_back({nup.first, mx_yl}); return true; } for (int i = dn.first; i <= dn.second; i++) { int mx_lt = pref[i - 1], mx_rt = suf[i + 1]; pair<int, int> nup = intersection(up, intersection(pref_ver[i - 1], suf_ver[i + 1])); if (nup.first > nup.second) { continue; } int y_rt = min(mx_rt, suf_hor[0].second); y_rt = min(y_rt, rt.second); if (y_rt < rt.first) { continue; } pair<int, int> nlt = intersection(lt, suf_hor[y_rt + 1]); if (nlt.first > nlt.second) { continue; } int y_lt = nlt.second; nup = intersection(nup, make_pair(suf_rt[y_rt + 1], suf_lt[y_lt + 1])); if (nup.first > nup.second) { continue; } ans.push_back({i, mn_yr}); ans.push_back({mn_xr, y_lt}); ans.push_back({mx_xl, y_rt}); ans.push_back({nup.first, mx_yl}); return true; } } return false; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { R r; cin >> r.xl >> r.yl >> r.xr >> r.yr; vx.push_back(r.xl); vx.push_back(r.xr); vy.push_back(r.yl); vy.push_back(r.yr); rcs.push_back(r); } vx.push_back(-1); vx.push_back(INF); vy.push_back(-1); vy.push_back(INF); sort(all(vx)); vx.erase(unique(all(vx)), vx.end()); sort(all(vy)); vy.erase(unique(all(vy)), vy.end()); for (int i = 0; i < n; i++) { rcs[i].xl = lower_bound(all(vx), rcs[i].xl) - vx.begin(); rcs[i].xr = lower_bound(all(vx), rcs[i].xr) - vx.begin(); rcs[i].yl = lower_bound(all(vy), rcs[i].yl) - vy.begin(); rcs[i].yr = lower_bound(all(vy), rcs[i].yr) - vy.begin(); } solve(rcs, k); while (ans.size() < k) ans.push_back({1, 1}); for (auto p : ans) { cout << vx[p.first] << " " << vy[p.second] << "\n"; } return 0; }

Compilation message (stderr)

hamburg.cpp: In function 'bool solve(std::vector<R>, int)':
hamburg.cpp:183:17: warning: unused variable 'mx_rt' [-Wunused-variable]
  183 |                 mx_rt = suf[i + 1];
      |                 ^~~~~
hamburg.cpp:220:17: warning: unused variable 'mx_lt' [-Wunused-variable]
  220 |             int mx_lt = pref[i - 1],
      |                 ^~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:297:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  297 |     while (ans.size() < k)
      |            ~~~~~~~~~~~^~~
#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...