Submission #251341

#TimeUsernameProblemLanguageResultExecution timeMemory
251341imeimi2000Hamburg Steak (JOI20_hamburg)C++17
15 / 100
208 ms19908 KiB
#include <bits/stdc++.h> #define x first #define y second #define x1 x.x #define y1 x.y #define x2 y.x #define y2 y.y using namespace std; typedef pair<int, int> pii; typedef pair<pii, pii> ppp; const int inf = 1e9 + 5; void flip_x(ppp &i) { swap(i.x1, i.x2); i.x1 = inf - i.x1; i.x2 = inf - i.x2; } void flip_y(ppp &i) { swap(i.y1, i.y2); i.y1 = inf - i.y1; i.y2 = inf - i.y2; } struct get_min { vector<pii> V; void add(int p, int x) { V.emplace_back(p, x); } void init() { V.emplace_back(-5, inf); sort(V.begin(), V.end()); int mn = inf; for (pii &i : V) { mn = min(mn, i.y); i.y = mn; } } int find(int x) const { return (lower_bound(V.begin(), V.end(), pii(x, -inf)) - 1)->y; } }; vector<pii> solve4(vector<ppp> R, int l, int d, int r, int u) { // l > r and u > d int l1 = d, l2 = u; int d1 = l, d2 = r; int r1 = d, r2 = u; int u1 = l, u2 = r; get_min ld, dr, ru, ul, rl, du; vector<int> cp; for (ppp &i : R) { i.x1 = max(i.x1, l); i.y1 = max(i.y1, d); i.x2 = min(i.x2, r); i.y2 = min(i.y2, u); int in_l = i.x1 == l, in_d = d == i.y1; int in_r = i.x2 == r, in_u = u == i.y2; int cnt = in_l + in_d + in_r + in_u; if (in_l) cp.push_back(i.y1), cp.push_back(i.y2); if (cnt > 2) continue; if (cnt == 1) { if (in_l) { l1 = max(l1, i.y1); l2 = min(l2, i.y2); } if (in_d) { d1 = max(d1, i.x1); d2 = min(d2, i.x2); } if (in_r) { r1 = max(r1, i.y1); r2 = min(r2, i.y2); } if (in_u) { u1 = max(u1, i.x1); u2 = min(u2, i.x2); } continue; } if (in_l && in_r) { l1 = max(l1, i.y1); r2 = min(r2, i.y2); rl.add(i.y2, -i.y1); continue; } if (in_d && in_u) { u1 = max(u1, i.x1); d2 = min(d2, i.x2); du.add(i.x2, -i.x1); continue; } if (in_l && in_d) ld.add(i.y2 - d, i.x2 - l); if (in_d && in_r) dr.add(r - i.x1, i.y2 - d); if (in_r && in_u) ru.add(u - i.y1, r - i.x1); if (in_u && in_l) ul.add(i.x2 - l, u - i.y1); } ld.init(); dr.init(); ru.init(); ul.init(); sort(cp.rbegin(), cp.rend()); cp.erase(unique(cp.begin(), cp.end()), cp.end()); vector<pii> ret; for (int ly : cp) { if (ly < l1 || l2 < ly) continue; int dx = min(d2, l + ld.find(ly - d)); if (dx < d1) continue; int ry = min(r2, d + dr.find(r - dx)); if (ry < r1) continue; if (ly > ry && ry < -rl.find(ly)) continue; int ux = max(u1, r - ru.find(u - ry)); if (u2 < ux) continue; if (dx < ux && dx < -du.find(ux)) continue; if (u - ul.find(ux - l) < ly) continue; ret.emplace_back(l, ly); ret.emplace_back(dx, d); ret.emplace_back(r, ry); ret.emplace_back(ux, u); break; } return ret; } vector<pii> solve(vector<ppp> R, int k) { if (R.empty()) return vector<pii>(k, pii(1, 1)); int l = inf, d = inf, r = 0, u = 0; for (ppp i : R) { l = min(l, i.x2); d = min(d, i.y2); r = max(r, i.x1); u = max(u, i.y1); } if (k == 1) { vector<pii> ret; if (r <= l && u <= d) ret.emplace_back(l, d); return ret; } for (int x : { l, r }) for (int y : { d, u }) { vector<ppp> nxt; for (ppp i : R) { if (i.x1 <= x && x <= i.x2 && i.y1 <= y && y <= i.y2) continue; nxt.push_back(i); } vector<pii> ret = solve(nxt, k - 1); if (ret.empty()) continue; ret.emplace_back(x, y); return ret; } if (k <= 3) return vector<pii>(); assert(l < r && d < u); for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { vector<pii> ans = solve4(R, l, d, r, u); if (!ans.empty()) { for (pii &p : ans) { if (i) p.x = inf - p.x; if (j) p.y = inf - p.y; } return ans; } for (ppp &i : R) flip_y(i); swap(d, u); d = inf - d; u = inf - u; } for (ppp &i : R) flip_x(i); swap(l, r); l = inf - l; r = inf - r; } return vector<pii>(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; vector<ppp> R(n); for (int i = 0; i < n; ++i) { cin >> R[i].x1 >> R[i].y1 >> R[i].x2 >> R[i].y2; } vector<pii> ans = solve(R, k); if (ans.empty()) return 1; for (pii i : ans) printf("%d %d\n", i.x, i.y); 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...