#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
template <class T, class... U> void bug_h(const T& t, const U&... u) { cerr << t; ((cerr << " | " << u), ...); cerr << endl; }
#define bug(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; bug_h(__VA_ARGS__)
#else
#define cerr if (false) cerr
#define bug(...)
#endif
#define ar array
#define all(v) std::begin(v), std::end(v)
#define sz(v) int(std::size(v))
typedef long long i64;
typedef vector<int> vi;
typedef pair<int, int> pi;
const int INF = 1e9;
int N, K;
vector<ar<int, 4>> rect;
vector<bool> covered;
vector<pi> solutions;
ar<int, 4> get_bounds() {
int x1 = INF, x2 = 1, y1 = INF, y2 = 1;
for (int i = 0; i < N; i++) if (!covered[i]) {
auto [l, d, r, u] = rect[i];
x1 = min(x1, r);
x2 = max(x2, l);
y1 = min(y1, u);
y2 = max(y2, d);
}
return {x1, x2, y1, y2};
}
void pr() {
for (auto [x, y] : solutions) cout << x << ' ' << y << '\n';
exit(0);
}
void rec(int k) {
if (!k) {
if (count(begin(covered), end(covered), 1) == N) pr();
return;
}
auto [x1, x2, y1, y2] = get_bounds();
for (auto x : {x1, x2}) for (auto y : {y1, y2}) {
solutions.push_back({x, y});
vector<int> add;
for (int i = 0; i < N; i++) if (!covered[i]) {
auto [l, d, r, u] = rect[i];
if (l <= x && x <= r && d <= y && y <= r) add.push_back(i);
}
for (int i : add) covered[i] = 1;
rec(k - 1);
for (int i : add) covered[i] = 0;
solutions.pop_back();
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> N >> K;
rect.resize(N);
for (auto &[l, d, r, u] : rect) {
cin >> l >> d >> r >> u;
}
covered.resize(N);
rec(K);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
348 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
72 ms |
12412 KB |
Output is correct |
6 |
Incorrect |
69 ms |
13112 KB |
Unexpected end of file - int32 expected |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
4 ms |
348 KB |
Unexpected end of file - int32 expected |
2 |
Halted |
0 ms |
0 KB |
- |