Submission #414530

#TimeUsernameProblemLanguageResultExecution timeMemory
414530usachevd0Hamburg Steak (JOI20_hamburg)C++17
15 / 100
395 ms29432 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() #define Time (clock() * 1.0 / CLOCKS_PER_SEC) using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1& x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1& x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) cerr << a[i] << ' '; cerr << endl; } #ifdef LOCAL #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) { for (auto& x : v) stream << x << ' '; return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const int INF32 = 1e9; using Point = array<int, 2>; struct Rect { int c[2][2]; Rect() {} void read() { cin >> c[0][0] >> c[1][0] >> c[0][1] >> c[1][1]; } bool in(Point P) { return c[0][0] <= P[0] && P[0] <= c[0][1] && c[1][0] <= P[1] && P[1] <= c[1][1]; } } universe_rect; Rect intersect(const Rect& r1, const Rect& r2) { Rect r3; for (int a = 0; a < 2; ++a) { r3.c[a][0] = max(r1.c[a][0], r2.c[a][0]); r3.c[a][1] = min(r1.c[a][1], r2.c[a][1]); } return r3; } vector<Point> solve(int k, vector<Rect> rects, vector<Point> points) { if (rects.empty()) { while (k--) points.push_back({0, 0}); return points; } Rect I = universe_rect; for (Rect& r : rects) I = intersect(I, r); if (k == 1) { if (I.c[0][0] > I.c[0][1] || I.c[1][0] > I.c[1][1]) { return {}; } else { points.push_back({I.c[0][0], I.c[1][0]}); return points; } } for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { Point P{I.c[0][i], I.c[1][j]}; points.push_back(P); vector<Rect> new_rects; for (auto r : rects) if (!r.in(P)) new_rects.push_back(r); auto res = solve(k - 1, new_rects, points); if (!res.empty()) { return res; } points.pop_back(); } } return {}; } int32_t main() { #ifdef LOCAL freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); universe_rect.c[0][0] = universe_rect.c[1][0] = 0; universe_rect.c[0][1] = universe_rect.c[1][1] = +INF32; int n, k; cin >> n >> k; vector<int> X[2]; vector<Rect> rects(n); for (auto& r : rects) { r.read(); for (int a = 0; a < 2; ++a) for (int b = 0; b < 2; ++b) X[a].push_back(r.c[a][b]); } for (int a = 0; a < 2; ++a) { sort(all(X[a])); X[a].resize(unique(all(X[a])) - X[a].begin()); } for (auto& r : rects) for (int a = 0; a < 2; ++a) for (int b = 0; b < 2; ++b) r.c[a][b] = lower_bound(all(X[a]), r.c[a][b]) - X[a].begin(); auto easy = solve(k, rects, {}); if (!easy.empty()) { for (auto P : easy) cout << X[0][P[0]] << ' ' << X[1][P[1]] << '\n'; exit(0); } assert(k == 4); Rect I = universe_rect; for (Rect& r : rects) I = intersect(I, r); assert(I.c[0][1] < I.c[0][0]); assert(I.c[1][1] < I.c[1][0]); 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...