Submission #1137731

#TimeUsernameProblemLanguageResultExecution timeMemory
1137731RaresFelixHamburg Steak (JOI20_hamburg)C++20
100 / 100
1602 ms153620 KiB
#include <bits/stdc++.h> //#pragma GCC optimize("O3") //#pragma GCC target("avx,avx2,fma") using namespace std; #define int ll using ll = long long; using vi = vector<int>; using ii = pair<int, int>; using vll = vector<ll>; const int INF = 1e9; struct steak { ii h, v; bool inside(ii pct) { return h.first <= pct.first && pct.first <= h.second && v.first <= pct.second && pct.second <= v.second; } }; tuple<int, int, int, int> get_steak_extremums(vector<steak> S) { auto seg_extremums = [&](vector<ii> V) { int l = -INF, r = INF; for(auto [s, d] : V) { l = max(l, s); r = min(r, d); } return ii{l, r}; }; vector<ii> H, V; for(auto [h, v] : S) { H.push_back(h); V.push_back(v); } auto [lh, rh] = seg_extremums(H); auto [lv, rv] = seg_extremums(V); return {lh, rh, lv, rv}; } vector<ii> sol_k1(vector<steak> S) { auto [lh, rh, lv, rv] = get_steak_extremums(S); if(lh <= rh && lv <= rv) return vector<ii>{ii{lh, lv}}; return vector<ii>(); } vector<ii> sol_k2(vector<steak> S) { ///will return the solution if it satisfies everyone auto [lh, rh, lv, rv] = get_steak_extremums(S); vector<ii> re; auto check_sol = [&](ii p1, ii p2) -> bool{ bool ok = true; for(auto it : S) { ok &= it.inside(p1) || it.inside(p2); if(!ok) break; } if(ok) { re = vector<ii>{p1, p2}; } return ok; }; check_sol(ii{lh, lv}, ii{rh, rv}); check_sol(ii{lh, rv}, ii{rh, lv}); return re; } vector<ii> sol_k3(vector<steak> S) { ///will return the solution if it satisfies everyone auto [lh, rh, lv, rv] = get_steak_extremums(S); vector<ii> Re; auto check_rest = [&](ii p) { vector<steak> LeftOver; for(auto it : S) if(!it.inside(p)) LeftOver.push_back(it); auto Cur = sol_k2(LeftOver); if(!Cur.empty()) { Cur.push_back(p); Re = Cur; } }; vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, }; for(auto it : Corners) check_rest(it); return Re; } vector<pair<int, ii> > get_intersect(steak x, vector<ii> &Corners) { ///returns a vector of (edge id, (min max allowed)) auto get_overlap0 = [&](ii seg, int l, int r) { if(l > r) swap(l, r); return ii{max(l, seg.first), min(r, seg.second)}; }; auto inside_seg = [&](int p, ii seg) { return seg.first <= p && p <= seg.second; }; auto get_overlap = [&](ii p1, ii p2) { if(p1.first == p2.first) { if(inside_seg(p1.first, x.h)) return get_overlap0(x.v, p1.second, p2.second); else return ii{1, 0}; } else { if(inside_seg(p1.second, x.v)) return get_overlap0(x.h, p1.first, p2.first); else return ii{1, 0}; } }; vector<pair<int, ii> > Re; for(int i = 0; i < 4; ++i) { auto re = get_overlap(Corners[i], Corners[(i + 1) % 4]); if(re.first <= re.second) Re.push_back({i, re}); } return Re; } ii intersect(ii a, ii b) { return {max(a.first, b.first), min(a.second, b.second)}; } struct RestrictionDS { int n; ii re; vector<ii> Re; vector<pair<ii, ii> > V; void add(ii x1, ii x2) { ///if a in x1 -> b in x2 V.push_back({x1, x2}); } void init(int N) { n = N; Re.resize(n, {-INF, INF}); vector<vector<ii> > Add(n), Rem(n); for(auto [x1, x2] : V) { auto [s, d] = x1; Add[s].push_back(x2); Rem[d].push_back(x2); } multiset<int> Low, High; for(int i = 0; i < n; ++i) { for(auto [l, r] : Add[i]) { Low.insert(l); High.insert(r); } int st = -INF, dr = INF; if(!Low.empty()) st = *Low.rbegin(); if(!High.empty()) dr = *High.begin(); Re[i] = {st, dr}; for(auto [l, r] : Rem[i]) { Low.erase(Low.find(l)); High.erase(High.find(r)); } } } ii eval(int p) { return Re[p]; } }; vector<ii> sol_k4_special(vector<steak> S) { vi X_posib, Y_posib; for(auto [h, v] : S) { X_posib.push_back(h.first); X_posib.push_back(h.second); Y_posib.push_back(v.first); Y_posib.push_back(v.second); } auto norm_vec = [&](vi &V) -> pair<int, map<int, int> > { sort(V.begin(), V.end()); V.resize(unique(V.begin(), V.end()) - V.begin()); int len = (int)V.size(); map<int, int> vti; for(int i = 0; i < len; ++i) { vti[V[i]] = i; } return {len, vti}; }; auto [len_x, vti_x] = norm_vec(X_posib); auto [len_y, vti_y] = norm_vec(Y_posib); for(auto &[h, v] : S) { h.first = vti_x[h.first]; h.second = vti_x[h.second]; v.first = vti_y[v.first]; v.second = vti_y[v.second]; } auto [lh, rh, lv, rv] = get_steak_extremums(S); vector<ii> Corners = { {rh, rv}, {rh, lv}, {lh, lv}, {lh, rv}, }; vector<ii> FullSeg = { {rv, lv}, {rh, lh}, {rv, lv}, {rh, lh}, }; /// for negations auto negate = [&](ii seg, ii full) { assert(seg.first <= seg.second); vector<ii> Rez; if(seg.second < full.second) Rez.push_back({seg.second + 1, full.second}); if(full.first < seg.first) Rez.push_back({full.first, seg.first - 1}); return Rez; }; vector<ii> RestrictiiInit; for(int i = 0; i < 4; ++i) { RestrictiiInit.push_back(FullSeg[i]); } array<array<RestrictionDS, 4>, 4> Forbid; vi Order = {0, 3, 1, 2}, RankOrd = {0, 2, 3, 1}; for(auto x : S) { int nrc = 0; for(auto p : Corners) nrc += x.inside(p); if(nrc > 1) { /// contains one whole edge; is surely covered continue; } auto Inter = get_intersect(x, Corners); assert(0 < Inter.size() && Inter.size() <= 2); if(Inter.size() == 1) { ///simple restriction ///Basic[Inter[0].first].add(ii{0, 0}, Inter[0].second); RestrictiiInit[Inter[0].first] = intersect(RestrictiiInit[Inter[0].first], Inter[0].second); } else { if(RankOrd[Inter[0].first] > RankOrd[Inter[1].first]) swap(Inter[0], Inter[1]); auto [id0, seg0] = Inter[0]; auto [id1, seg1] = Inter[1]; for(auto it : negate(seg0, FullSeg[id0])) Forbid[id0][id1].add(it, seg1); if(id0 % 2 == id1 % 2 && id0 == 3) { /// grava RestrictiiInit[id0] = intersect(RestrictiiInit[id0], {rh, seg1.second}); RestrictiiInit[id1] = intersect(RestrictiiInit[id1], {seg1.first, lh}); // Basic[id0].add({0, 0}, {rh, seg1.second}); // Basic[id1].add({0, 0}, {seg1.first, lh}); } } } for(int i = 0; i < 4; ++i) { for(int j = i + 1; j < 4; ++j) { ///Forbid[Ord[i]][Ord[j]] if(Order[i] % 2 == 1) { Forbid[Order[i]][Order[j]].init(len_x); } else { Forbid[Order[i]][Order[j]].init(len_y); } } } for(int x0 = 0; x0 < len_y; ++x0) { ///now choose the others greedly vector<ii> Rest = RestrictiiInit; vi X(4, 0); X[0] = x0; bool ok = true; for(int i = 1; i < 4; ++i) { for(int j = i; j < 4; ++j) { /// process what Order[i - 1] did for everyone ii new_rest = Forbid[Order[i - 1]][Order[j]].eval(X[Order[i - 1]]); Rest[Order[j]] = intersect(Rest[Order[j]], new_rest); } if(Rest[Order[i]].first > Rest[Order[i]].second) { ok = false; break; } X[Order[i]] = Rest[Order[i]].second; } if(!ok) continue; for(int i = 0; i < 4; ++i) ok &= Rest[i].first <= X[i] && X[i] <= Rest[i].second; if(ok) { ///avem o solutie vector<ii> Re = {{rh, X[0]}, {X[1], lv}, {lh, X[2]}, {X[3], rv}}; for(auto &[x, y] : Re) { x = X_posib[x]; y = Y_posib[y]; } return Re; } } return vector<ii>(); } vector<ii> sol_k4(vector<steak> S) { ///will return the solution if it satisfies everyone auto [lh, rh, lv, rv] = get_steak_extremums(S); vector<ii> Re; auto check_rest = [&](ii p) { vector<steak> LeftOver; for(auto it : S) if(!it.inside(p)) LeftOver.push_back(it); auto Cur = sol_k3(LeftOver); if(!Cur.empty()) { Cur.push_back(p); Re = Cur; } }; vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, }; for(auto p : Corners) check_rest(p); if(!Re.empty()) return Re; /// now we're sure no corners are used Re = sol_k4_special(S); if(!Re.empty()) return Re; for(auto &it : S) { it.v.first *= -1; it.v.second *= -1; swap(it.v.first, it.v.second); } Re = sol_k4_special(S); assert(!Re.empty()); for(auto &[x, y] : Re) y *= -1; for(auto &it : S) { it.v.first *= -1; it.v.second *= -1; swap(it.v.first, it.v.second); } for(auto x : S) { bool ok = false; for(auto it : Re) { ok |= x.inside(it); } assert(ok); } return Re; } signed main() { cin.tie(0); ios_base::sync_with_stdio(0); int n, k; cin >> n >> k; vector<steak> S(n); for(int i = 0; i < n; ++i) { cin >> S[i].h.first >> S[i].v.first >> S[i].h.second >> S[i].v.second; } vector<ii> Re; if(k == 1) Re = sol_k1(S); if(k == 2) Re = sol_k2(S); if(k == 3) Re = sol_k3(S); if(k == 4) Re = sol_k4(S); for(auto it : Re) cout << it.first << " " << it.second << "\n"; 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...