Submission #484436

#TimeUsernameProblemLanguageResultExecution timeMemory
484436valerikkHamburg Steak (JOI20_hamburg)C++17
15 / 100
3029 ms27556 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9; struct Rect { int l, d, r, u; bool operator()(int x, int y) { return l <= x && x <= r && d <= y && y <= u; } }; vector<Rect> filter(vector<Rect> rects, int x, int y) { vector<Rect> res; for (auto r : rects) { if (!r(x, y)) { res.push_back(r); } } return res; } void out(int k, vector<pair<int, int>> points) { for (int i = 0; i < k; ++i) { auto [x, y] = points[min(i, (int)points.size() - 1)]; cout << x << " " << y << "\n"; } exit(0); } void rec(vector<Rect> rects, int k, vector<pair<int, int>> points) { for (auto [x, y] : points) { rects = filter(rects, x, y); } if (rects.empty()) { out(k, points); } if ((int)points.size() == k) { return; } int maxl = 1, minr = INF, maxd = 1, minu = INF; for (auto r : rects) { maxl = max(maxl, r.l); minr = min(minr, r.r); maxd = max(maxd, r.d); minu = min(minu, r.u); } if (maxd <= minu) { sort(rects.begin(), rects.end(), [&](Rect r1, Rect r2) { return r1.r < r2.r; }); for (auto r : rects) { bool ok = false; for (auto [x, y] : points) { ok |= r(x, y); } if (!ok) { if ((int)points.size() == k) { return; } points.push_back({r.r, maxd}); } } out(k, points); } if (k == 1) { return; } if (maxl <= minr) { sort(rects.begin(), rects.end(), [&](Rect r1, Rect r2) { return r1.u < r2.u; }); for (auto r : rects) { bool ok = false; for (auto [x, y] : points) { ok |= r(x, y); } if (!ok) { if ((int)points.size() == k) { return; } points.push_back({maxl, r.u}); } } out(k, points); } if (k == 4 && points.empty()) { points.push_back({maxl, maxd}); rec(rects, k, points); points.pop_back(); for (auto r : rects) { points.push_back({maxl, r.d}); rec(rects, k, points); points.pop_back(); } } else { for (int x : {maxl, minr}) { for (int y : {maxd, minu}) { points.push_back({x, y}); rec(rects, k, points); points.pop_back(); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<Rect> rects(n); for (auto &r : rects) { cin >> r.l >> r.d >> r.r >> r.u; } vector<pair<int, int>> points; rec(rects, k, points); 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...