Submission #223777

#TimeUsernameProblemLanguageResultExecution timeMemory
223777MinnakhmetovHamburg Steak (JOI20_hamburg)C++14
15 / 100
396 ms26924 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(aaa) aaa.begin(), aaa.end() const int N = 4e5 + 5; struct R { int xl, yl, xr, yr; bool contains(int x, int y) const { return x >= xl && x <= xr && y >= yl && y <= yr; } }; vector<R> rcs; vector<int> vx, vy; vector<pair<int, int>> ans; 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); } // cout << mn_xr << " " << mn_yr << " " << mx_xl << " " << mx_yl << "\n"; // exit(0); 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; assert(k == 4); } 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); } 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({0, 0}); for (auto p : ans) { cout << vx[p.first] << " " << vy[p.second] << "\n"; } return 0; }

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:142: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]
  142 |     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...