#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 (x == k) {
if (check()) {
//cout << "I FOUND IT \n";
//cout << "\\TODO\n";
for (auto p: points) {
cout << X[p.first] << ' ' << Y[p.second] << '\n';
}
exit(0);
}
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++) {
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());
//random_shuffle(p.begin(), p.end());
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 time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19412 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
12 ms |
19376 KB |
Output is correct |
| 4 |
Correct |
13 ms |
19412 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19400 KB |
Output is correct |
| 2 |
Correct |
14 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 4 |
Correct |
13 ms |
19420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19348 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19444 KB |
Output is correct |
| 5 |
Correct |
14 ms |
19412 KB |
Output is correct |
| 6 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 7 |
Correct |
16 ms |
19412 KB |
Output is correct |
| 8 |
Correct |
14 ms |
19284 KB |
Output is correct |
| 9 |
Correct |
14 ms |
19396 KB |
Output is correct |
| 10 |
Incorrect |
14 ms |
19284 KB |
Expected integer, but "NO" found |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19416 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 4 |
Correct |
14 ms |
19356 KB |
Output is correct |
| 5 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 6 |
Correct |
14 ms |
19412 KB |
Output is correct |
| 7 |
Correct |
16 ms |
19284 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
19340 KB |
Expected integer, but "NO" found |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
19412 KB |
Output is correct |
| 2 |
Correct |
12 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
12 ms |
19376 KB |
Output is correct |
| 4 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 5 |
Correct |
508 ms |
47416 KB |
Output is correct |
| 6 |
Correct |
494 ms |
47356 KB |
Output is correct |
| 7 |
Correct |
525 ms |
47448 KB |
Output is correct |
| 8 |
Correct |
478 ms |
47296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19400 KB |
Output is correct |
| 2 |
Correct |
14 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 4 |
Correct |
13 ms |
19420 KB |
Output is correct |
| 5 |
Correct |
536 ms |
41940 KB |
Output is correct |
| 6 |
Incorrect |
547 ms |
45016 KB |
Expected integer, but "NO" found |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19348 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19444 KB |
Output is correct |
| 5 |
Correct |
14 ms |
19412 KB |
Output is correct |
| 6 |
Correct |
13 ms |
19412 KB |
Output is correct |
| 7 |
Correct |
16 ms |
19412 KB |
Output is correct |
| 8 |
Correct |
14 ms |
19284 KB |
Output is correct |
| 9 |
Correct |
14 ms |
19396 KB |
Output is correct |
| 10 |
Incorrect |
14 ms |
19284 KB |
Expected integer, but "NO" found |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 2 |
Correct |
13 ms |
19416 KB |
Output is correct |
| 3 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 4 |
Correct |
14 ms |
19356 KB |
Output is correct |
| 5 |
Correct |
13 ms |
19284 KB |
Output is correct |
| 6 |
Correct |
14 ms |
19412 KB |
Output is correct |
| 7 |
Correct |
16 ms |
19284 KB |
Output is correct |
| 8 |
Incorrect |
17 ms |
19340 KB |
Expected integer, but "NO" found |
| 9 |
Halted |
0 ms |
0 KB |
- |
