제출 #212117

#제출 시각아이디문제언어결과실행 시간메모리
212117IOrtroiii함박 스테이크 (JOI20_hamburg)C++14
21 / 100
3062 ms11140 KiB
#include <bits/stdc++.h> using namespace std; const int INF = 1e9; using Rect = array<int, 4>; const Rect FULL = {0, 0, INF, INF}; Rect inter(const Rect &l, const Rect &r) { return {max(l[0], r[0]), max(l[1], r[1]), min(l[2], r[2]), min(l[3], r[3])}; } mt19937 rng((uint32_t) chrono::steady_clock::now().time_since_epoch().count()); int main() { ios_base::sync_with_stdio(false); int N, K; cin >> N >> K; vector<Rect> A(N), ans(K); for (int i = 0; i < N; ++i) { cin >> A[i][0] >> A[i][1] >> A[i][2] >> A[i][3]; } while (true) { vector<Rect> goods, bads; for (int z = 0; z < K; ++z) ans[z] = FULL; for (auto r : A) { bool ok = false; for (int z = 0; z < K; ++z) { Rect nans = inter(ans[z], r); if (nans[0] <= nans[2] && nans[1] <= nans[3]) { ans[z] = nans; goods.emplace_back(r); ok = true; break; } } if (!ok) bads.emplace_back(r); } if (bads.empty()) break; A = bads; shuffle(A.begin(), A.end(), rng); A.insert(A.end(), goods.begin(), goods.end()); } for (int z = 0; z < K; ++z) { cout << ans[z][0] << " " << ans[z][1] << "\n"; } }
#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...