이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define ar array
const int mxN=2e5;
int n, k, d[mxN], b[mxN];
ar<int, 4> a[mxN], p[4];
ar<int, 4> ir{1, 1, INT_MAX, INT_MAX};
vector<int> v1, v2;
ar<int, 4> it(ar<int, 4> a, ar<int, 4> b) {
return {max(a[0], b[0]), max(a[1], b[1]), min(a[2], b[2]), min(a[3], b[3])};
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<long long>(L, R)(rng);
cin >> n >> k;
for(int i=0; i<n; ++i) {
cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
v2.push_back(i);
}
while(1){
vector<int> u=v2; v2.clear();
for(int i=0; i<k; ++i) p[i]=ir;
for(int i=0; i<n; ++i) {
bool ok=0;
for(int j=0; j<k; ++j) {
ar<int, 4> bl=it(p[j], a[u[i]]);
if(bl[0]<=bl[2]&&bl[1]<=bl[3]) {
p[j]=bl; v1.push_back(u[i]); ok=1; break;
}
}
if(!ok) v2.push_back(u[i]);
}
if(v2.empty()) {
for(int j=0; j<k; ++j)
cout << p[j][0] << " " << p[j][1] << "\n";
break;
}
shuffle(all(v2),rng); reverse(all(v2)); v2.insert(v2.end(), all(v1)); v1.clear();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |