Submission #217247

#TimeUsernameProblemLanguageResultExecution timeMemory
217247ToadologistHamburg Steak (JOI20_hamburg)C++11
2 / 100
325 ms8720 KiB
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> pii; #ifdef DEBUG #define display(x) cerr << #x << " = " << x << endl; #define displaya(a, st, n)\ {cerr << #a << " = {";\ for(int qwq = (st); qwq <= (n); ++qwq) {\ if(qwq == (st)) cerr << a[qwq];\ else cerr << ", " << a[qwq];\ } cerr << "}" << endl;} #define displayv(v) displaya(v, 0, (int)(v).size() - 1) #define eprintf(...) fprintf(stderr, __VA_ARGS__) #else #define display(x) ; #define displaya(a, st, n) ; #define displayv(v) ; #define eprintf(...) if(0) fprintf(stderr, "...") #endif template<typename T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; } template<typename T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; } template<typename A, typename B> ostream& operator << (ostream& out, const pair<A, B> &p) { return out << '(' << p.first << ", " << p.second << ')'; } const int maxN = 200000 + 5; struct Rect { int L, D, R, U; Rect(int l, int d, int r, int u) : L(l), D(d), R(r), U(u) {} LL area() const { return (LL)max(0, R - L + 1) * (LL)max(0, U - D + 1); } bool hit(pii p) const { return L <= p.first && p.first <= R && D <= p.first && p.first <= U; } }; int nx, ny; vector<int> tx, ty; Rect com(Rect x, Rect y) { return Rect(max(x.L, y.L), max(x.D, y.D), min(x.R, y.R), min(x.U, y.U)); } void disc(vector<Rect> &v) { { vector<int> &t = tx; t.clear(); for(auto r : v) t.push_back(r.L), t.push_back(r.R); sort(t.begin(), t.end()); t.erase(unique(t.begin(), t.end()), t.end()); for(auto &r : v) r.L = lower_bound(t.begin(), t.end(), r.L) - t.begin() + 1, r.R = lower_bound(t.begin(), t.end(), r.R) - t.begin() + 1; nx = t.size(); } { vector<int> &t = ty; t.clear(); for(auto r : v) t.push_back(r.D), t.push_back(r.U); sort(t.begin(), t.end()); t.erase(unique(t.begin(), t.end()), t.end()); for(auto &r : v) r.D = lower_bound(t.begin(), t.end(), r.D) - t.begin() + 1, r.U = lower_bound(t.begin(), t.end(), r.U) - t.begin() + 1; ny = t.size(); } } vector<Rect> ans; vector<int> oned(vector<pii> &v) { vector<int> res; sort(v.begin(), v.end()); int last = max(nx, ny) + 1; for(int i = (int)v.size() - 1; i >= 0; --i) { if(v[i].first <= last && last <= v[i].second) continue; else res.push_back(last = v[i].first); } return res; } bool solve(vector<Rect> &v, int k, vector<pii> &res) { res.clear(); { // k == 0 if(v.size() == 0) return true; if(k <= 0) return false; } Rect c(1, 1, nx, ny); for(auto r : v) c = com(c, r); { // k == 1 if(c.area() > 0) { res.emplace_back(c.L, c.D); return true; } if(k <= 1) return false; } if(c.L <= c.R) { vector<pii> segs; for(int i = 0; i < (int)v.size(); ++i) segs.emplace_back(v[i].D, v[i].U); vector<int> pos = oned(segs); if((int)pos.size() > k) return false; for(auto p : pos) res.emplace_back(c.L, p); return true; } if(c.D <= c.U) { vector<pii> segs; for(int i = 0; i < (int)v.size(); ++i) segs.emplace_back(v[i].L, v[i].R); vector<int> pos = oned(segs); if((int)pos.size() > k) return false; for(auto p : pos) res.emplace_back(p, c.D); return true; } { // k == 2 auto check = [&](pii x, pii y) { for(auto r : v) { if(!r.hit(x) && !r.hit(y)) return false; } res.push_back(x); res.push_back(y); return true; }; if(check(pii(c.L, c.D), pii(c.R, c.U))) return true; if(check(pii(c.L, c.U), pii(c.R, c.D))) return true; if(k <= 2) return false; } { // k == 3 auto check = [&](pii x) { vector<Rect> nv; vector<pii> sol; for(auto r : v) { if(!r.hit(x)) nv.push_back(r); } if(solve(nv, k - 1, sol)) { res.push_back(x); res.insert(res.end(), sol.begin(), sol.end()); return true; } return false; }; if(check(pii(c.L, c.D))) return true; if(check(pii(c.L, c.U))) return true; if(check(pii(c.R, c.D))) return true; if(check(pii(c.R, c.U))) return true; if(k <= 3) return false; } { } return false; } int main() { #ifndef LOCAL ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif int n, k; cin >> n >> k; vector<Rect> v; for(int i = 0; i < n; ++i) { int l, d, r, u; cin >> l >> d >> r >> u; v.emplace_back(l, d, r, u); } disc(v); for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U); vector<pii> res; bool ok = solve(v, k, res); assert(ok); while((int)res.size() < k) res.emplace_back(1, 1); for(auto p : res) cout << tx[p.first - 1] << " " << ty[p.second - 1] << endl; return 0; }

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:173:11: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  173 |  for(auto r : v) eprintf("rect %d %d %d %d\n", r.L, r.D, r.R, r.U);
      |           ^
#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...