#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];
void rec();
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 add_point(int x, int y) {
vector<int> change;
for (int i = used._Find_first(); i < n; i = used._Find_next(i)) {
if (inter(i, x, y)) {
used[i] = false;
change.push_back(i);
}
}
points.emplace_back(x, y);
rec();
for (auto cc: change) used[cc] = true;
points.pop_back();
}
void rec() {
if (check() && (int) points.size() <= k) {
for (int i = 0; i < (int) points.size(); i++)
cout << X[points[i].first] << ' ' << Y[points[i].second] << '\n';
for (int i = points.size(); i < k; i++)
cout << 1 << ' ' << 1 << '\n';
exit(0);
}
if (points.size() >= k)
return;
int minR = 2 * n;
int minU = 2 * n;
int maxD = 0;
int maxL = 0;
for (int i = used._Find_first(); i < n; i = used._Find_next(i)) {
minR = min(minR, r[i]);
maxL = max(maxL, l[i]);
minU = min(minU, u[i]);
maxD = max(maxD, d[i]);
}
if (maxL <= minR) {
add_point(minR, minU);
}
else if (maxD <= minU) {
add_point(minR, minU);
}
else {
add_point(minR, minU);
add_point(minR, maxD);
//add_point(maxL, minU);
//add_point(maxL, maxD);
if (points.size())
return;
for (int h = 0; h < Y.size(); h++)
add_point(minR, h);
}
}
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();
cout << "NO I DID NOT FIND ANYTHING\n";
return 0;
}
Compilation message
hamburg.cpp: In function 'void rec()':
hamburg.cpp:46:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | if (points.size() >= k)
| ~~~~~~~~~~~~~~^~~~
hamburg.cpp:75:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for (int h = 0; h < Y.size(); h++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19216 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19200 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19216 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19200 KB |
Expected integer, but "NO" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
