This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (0) 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;
struct SCC {
vector<vi> g, rg;
vi order, id, comps;
SCC(int n) : g(n), rg(n), id(n) {
exchange(order, {});
}
void make_edge(int i, int j) {
g.at(i).push_back(j);
rg.at(j).push_back(i);
}
void dfs1(int i) {
id[i] = 1;
for (int j : g[i]) if (!id[j]) dfs1(j);
order.push_back(i);
}
void dfs2(int i, int c) {
id[i] = c;
for (int j : g[i]) if (id[j] == -1) dfs2(j, c);
}
int solve() {
for (int i = 0; i < sz(id); i++) if (!id[i]) dfs1(i);
reverse(all(order)), fill(all(id), -1);
int c = 0;
for (int i = 0; i < sz(id); i++) if (id[i] == -1) dfs2(i, c++);
return c;
}
};
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(all(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 <= u) 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);
auto [x1, x2, y1, y2] = get_bounds();
vector<pi> edges;
int n = 0;
vector<ar<int, 3>> A, B, C, D;
for (int i = 0; i < N; i++) {
auto [l, d, r, u] = rect[i];
if (l <= x1 && x1 <= r && d <= y1 && y2 <= u) continue;
if (l <= x2 && x2 <= r && d <= y1 && y2 <= u) continue;
if (l <= x1 && x2 <= r && d <= y1 && y1 <= u) continue;
if (l <= x1 && x2 <= r && d <= y2 && y2 <= u) continue;
int cnt = 0;
if (d <= y1 && y1 <= u) {
assert(max(x1, l) <= min(x2, r));
A.push_back({max(x1, l), min(x2, r), i * 2 + cnt});
cnt++;
}
if (d <= y2 && y2 <= u) {
assert(max(x1, l) <= min(x2, r));
B.push_back({max(x1, l), min(x2, r), i * 2 + cnt});
cnt++;
}
if (l <= x1 && x1 <= r) {
assert(max(y1, d) <= min(y2, u));
C.push_back({max(y1, d), min(y2, u), i * 2 + cnt});
cnt++;
}
if (l <= x2 && x2 <= r) {
assert(max(y1, d) <= min(y2, u));
D.push_back({max(y1, d), min(y2, u), i * 2 + cnt});
cnt++;
}
if (cnt == 1) {
edges.push_back({i * 2, i * 2 + 1});
} else assert(cnt == 2);
}
auto process = [&](const vector<ar<int, 3>> v) {
auto one = v, two = v;
sort(all(one), [&](auto x, auto y) {
return x[1] < y[1];
});
sort(all(two), [&](auto x, auto y) {
return x[0] > y[0];
});
vi f(sz(v)), g(sz(v));
for (int i = 0; i < sz(v); i++) {
if (i == 0) {
f[i] = one[i][2] ^ 1;
g[i] = two[i][2] ^ 1;
} else {
f[i] = N * 2 + (n++);
g[i] = N * 2 + (n++);
edges.push_back({f[i], one[i][2] ^ 1});
edges.push_back({f[i], f[i - 1]});
edges.push_back({g[i], two[i][2] ^ 1});
edges.push_back({g[i], g[i - 1]});
}
}
for (auto [l, r, i] : v) {
if (one[0][1] < l) {
int low = 0, hi = sz(one) - 1;
while (low < hi) {
int m = (low + hi) / 2 + 1;
one[m][1] < l ? low = m : hi = m - 1;
}
edges.push_back({i, f[low]});
}
if (two[0][0] > r) {
int low = 0, hi = sz(two) - 1;
while (low < hi) {
int m = (low + hi) / 2 + 1;
two[m][0] > r ? low = m : hi = m - 1;
}
edges.push_back({i, g[low]});
}
}
};
process(A);
process(B);
process(C);
process(D);
SCC S(N * 2 + n);
for (auto [i, j] : edges) S.make_edge(i, j);
int CC = S.solve();
for (int i = 0; i < N; i++) assert(S.id[i * 2] != S.id[i * 2 + 1]);
vi what(CC, -1);
for (int i = 0; i < N * 2; i++) if (what[S.id[i]] == -1) {
what[S.id[i]] = 1;
what[S.id[i ^ 1]] = 0;
}
auto go = [&](const vector<ar<int, 3>> v) {
int x1 = INF, x2 = 1;
for (auto [l, r, i] : v) if (what[S.id[i]]) x1 = max(x1, l), x2 = min(x2, r);
assert(x1 <= x2);
return x1;
};
solutions.push_back({go(A), y1});
solutions.push_back({go(B), y2});
solutions.push_back({x1, go(C)});
solutions.push_back({x2, go(D)});
pr();
}
# | 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... |