Submission #213153

#TimeUsernameProblemLanguageResultExecution timeMemory
213153combi1k1Hamburg Steak (JOI20_hamburg)C++14
21 / 100
3081 ms6764 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld double #define sz(x) (int)x.size() #define all(x) x.begin(),x.end() #define pb emplace_back #define X first #define Y second const int N = 2e5 + 5; typedef pair<int,int> ii; struct Rec { int l, r; int u, d; } a[N]; Rec p[4]; Rec inf; Rec operator & (const Rec&a,const Rec&b) { Rec c; c.l = max(a.l,b.l); c.u = max(a.u,b.u); c.r = min(a.r,b.r); c.d = min(a.d,b.d); return c; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(NULL)); int n; cin >> n; int k; cin >> k; inf.l = inf.u = 1; inf.r = inf.d = 1e9 ; vector<int> v1; vector<int> v2; for(int i = 0 ; i < n ; ++i) { cin >> a[i].l >> a[i].u; cin >> a[i].r >> a[i].d; v2.push_back(i); } while (1) { vector<int> nxt = v2; v2.clear(); fill(p,p + k,inf); for(int i : nxt) { bool ok = 0; for(int j = 0 ; j < k ; ++j) { Rec T = p[j] & a[i]; if (T.l > T.r) continue; if (T.u > T.d) continue; p[j] = T; ok = 1; break; } if (ok) v1.pb(i); else v2.pb(i); } if (v2.empty()) { for(int i = 0 ; i < k ; ++i) cout << p[i].l << " " << p[i].u << "\n"; return 0; } random_shuffle(all(v2)); v2.insert(v2.end(),v1.begin(),v1.end()); v1.clear(); } } //https://codeforces.com/blog/entry/74871?#comment-590859
#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...