#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 50;
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[N], op[N];
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 < 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);
}
/*
cout << "NOT USED : \n";
for (int i = 0; i < n; i++) if (!used[i])
cout << i << ' ' << r[i] << '\n';
cout << "\nEND IF NOT USED\n";
cout << "MINR: " << minR << '\n';
*/
set<int> S;
vector<int> p;
for (int h = 0; h < 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();
}
}
}
/*
cout << "CANDIDATE POINTS: " << p.size() << '\n';
for (auto u: p)
cout << minR << ' ' << u << '\n';
cout << "END OF CANDIDATE POINTS\n";
*/
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);
points.pop_back();
//RESET:
for (auto cc: change) used[cc] = false;
}
}
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;
/*
cout << "POINTS: \n";
for (int i = 0; i < n; i++) {
cout << l[i] << ' ' << d[i] << ' ' << r[i] << ' ' << u[i] << '\n';
}
*/
rec(0);
cout << "NO I DID NOT FIND ANYTHING\n";
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
9940 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9948 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
9940 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
9960 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
9940 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9948 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
9940 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
7 ms |
9960 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
