Submission #648142

#TimeUsernameProblemLanguageResultExecution timeMemory
648142406Hamburg Steak (JOI20_hamburg)C++17
3 / 100
3085 ms40256 KiB
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 50; const int M = 2 * N + 5; int l[N], r[N], u[N], d[N], n, k; bitset<N> used, full; vector<pair<int, int>> points; vector<int> X, Y, cl[M], op[M]; inline bool check() { return used == full; } inline bool inter(int i, int x, int y) { return l[i] <= x && x <= r[i] && d[i] <= y && y <= u[i]; } void rec(int x) { if (check()) { for (int i = 0; i < (int) points.size(); i++) cout << X[points[i].first] << ' ' << Y[points[i].second] << '\n'; for (int i = points.size(); i < k; i++) cout << 1 << ' ' << 1 << '\n'; exit(0); } if (x == k) return; for (int i = 0; i <= 2 * n; i++) op[i].clear(), cl[i].clear(); int minR = 2 * n; for (int i = 0; i < n; i++) if (!used[i]) minR = min(minR, r[i]); for (int i = 0; i < n; i++) if (!used[i] && l[i] <= minR) { cl[u[i]].push_back(i); op[d[i]].push_back(i); } set<int> S; vector<int> p; for (int h = 0; h <= 2 * n; h++) { if (cl[h].size()) p.push_back(h); continue; for (auto u: op[h]) S.insert(u); for (auto v: cl[h]) { if (S.count(v)) { p.push_back(h); S.clear(); } } } /* assert(S.empty()); for (int h = 2 * n; h >= 0; h--) { for (auto u: cl[h]) S.insert(u); for (auto v: op[h]) { if (S.count(v)) { p.push_back(h); S.clear(); } } } */ /* sort(p.begin(), p.end()); p.resize(unique(p.begin(), p.end()) - p.begin()); */ for (auto h: p) { vector<int> change; for (int i = 0; i < n; i++) if (!used[i]) { if (inter(i, minR, h)) { used[i] = true; change.push_back(i); } } points.emplace_back(minR, h); rec(x + 1); //RESET: for (auto cc: change) used[cc] = false; points.pop_back(); } } signed main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; X.reserve(2 * n), Y.reserve(2 * n); for (int i = 0; i < n; i++) { cin >> l[i] >> d[i] >> r[i] >> u[i]; X.push_back(l[i]); X.push_back(r[i]); Y.push_back(d[i]); Y.push_back(u[i]); } sort(X.begin(), X.end()); X.resize(unique(X.begin(), X.end()) - X.begin()); sort(Y.begin(), Y.end()); Y.resize(unique(Y.begin(), Y.end()) - Y.begin()); for (int i = 0; i < n; i++) { l[i] = lower_bound(X.begin(), X.end(), l[i]) - X.begin(); r[i] = lower_bound(X.begin(), X.end(), r[i]) - X.begin(); u[i] = lower_bound(Y.begin(), Y.end(), u[i]) - Y.begin(); d[i] = lower_bound(Y.begin(), Y.end(), d[i]) - Y.begin(); } for (int i = 0; i < n; i++) full[i] = true; used = 0; rec(0); cout << "NO I DID NOT FIND ANYTHING\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...