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;
using pii = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pii>;
using vvi = vector<vi>;
const vector<pii> EMP = {};
int f(vi &X, int x) { return lower_bound(X.begin(), X.end(), x) - X.begin() + 1; }
vi X, Y; int XS, YS;
vvi rem(vvi &A, int x, int y) {
vvi ret;
for(auto& it: A) if(it[2] < x || x < it[0] || it[3] < y || y < it[1]) ret.push_back(it);
return ret;
}
vvi intersect_line(vvi &A, int x, int y) {
vvi ret;
if(x) for(auto& it: A) if(it[0] <= x || x <= it[2]) ret.push_back(it);
if(y) for(auto& it: A) if(it[1] <= y || y <= it[3]) ret.push_back(it);
return ret;
}
vpi sol4(vvi &A) {
int mnr = XS, mxl = 1, mnu = YS, mxd = 1;
for(auto& it: A) {
mnr = min(mnr, it[2]);
mxl = max(mxl, it[0]);
mnu = min(mnu, it[3]);
mxd = max(mxd, it[1]);
}
for(auto& it: A) if(mnr < it[0] && it[2] < mxl && mnu < it[1] && it[3] < mxd) return EMP;
vvi L = intersect_line(A, mxl, 0);
sort(L.begin(), L.end(), [&](vi p, vi q) { return p[3] < q[3]; });
vi D_mnr(YS + 1, XS + 1);
for(auto& it: L) D_mnr[it[3]] = min(D_mnr[it[3]], it[2]);
for(int i=1; i<=YS; i++) D_mnr[i] = min(D_mnr[i-1], D_mnr[i]);
sort(L.begin(), L.end(), [&](vi p, vi q) { return p[1] > q[1]; });
vi U_mnr(YS + 2, XS + 1);
for(auto& it: L) U_mnr[it[1]] = min(U_mnr[it[1]], it[2]);
for(int i=YS; i>=1; i--) U_mnr[i] = min(U_mnr[i+1], U_mnr[i]);
int new_mnr = XS + 1;
for(auto& it: A) if(mnr < it[0]) new_mnr = min(new_mnr, it[2]);
int only_D_mnr = XS + 1;
vvi D = intersect_line(A, 0, mnu);
for(auto& it: D) if(mnr < it[0] && it[3] < mxd) only_D_mnr = min(only_D_mnr, it[2]);
vvi UD = intersect_line(D, 0, mxd);
sort(UD.begin(), UD.end(), [&](vi p, vi q) { return p[0] > q[0]; });
vi UD_mnr(XS + 2, XS + 1);
for(auto& it: UD) UD_mnr[it[0]] = min(UD_mnr[it[0]], it[2]);
for(int i=XS; i>=1; i--) UD_mnr[i] = min(UD_mnr[i+1], UD_mnr[i]);
vvi R = intersect_line(A, mxl, 0); sort(R.begin(), R.end(), [&](vi p, vi q) { return p[0] > q[0]; });
vvi RU = intersect_line(R, 0, mxd); sort(RU.begin(), RU.end(), [&](vi p, vi q) { return p[0] > q[0]; });
vvi RD = intersect_line(R, 0, mnu); sort(RD.begin(), RD.end(), [&](vi p, vi q) { return p[0] > q[0]; });
vi RU_mxd(XS + 2, 0);
for(auto& it: RU) if(it[1] > mnu) RU_mxd[it[0]] = max(RU_mxd[it[0]], it[1]);
for(int i=XS; i>=1; i--) RU_mxd[i] = max(RU_mxd[i+1], RU_mxd[i]);
vi RD_mnu(XS + 2, YS + 1);
for(auto& it: RD) if(it[3] < mxd) RD_mnu[it[0]] = min(RD_mnu[it[0]], it[3]);
for(int i=XS; i>=1; i--) RD_mnu[i] = min(RD_mnu[i+1], RD_mnu[i]);
int only_R_mxd = 0, only_R_mnu = YS + 1;
for(auto& it: R) if(it[1] > mnu && it[3] < mxd) {
only_R_mxd = max(only_R_mxd, it[1]);
only_R_mnu = min(only_R_mnu, it[3]);
}
for(int ly=2; ly<YS; ly++) {
int ux = min(U_mnr[ly + 1], new_mnr);
int dx = min({D_mnr[ly - 1], only_D_mnr, UD_mnr[ux + 1]});
int r_mxd = max(RU_mxd[ux + 1], only_R_mxd);
int r_mnu = min(RD_mnu[dx + 1], only_R_mnu);
if(r_mxd <= r_mnu) return {{mnr, ly}, {ux, mxd}, {dx, mnu}, {mxl, r_mxd}};
}
return EMP;
}
vpi sol(vvi &A, int K) {
int mnr = XS, mxl = 1, mnu = YS, mxd = 1;
for(auto& it: A) {
mnr = min(mnr, it[2]);
mxl = max(mxl, it[0]);
mnu = min(mnu, it[3]);
mxd = max(mxd, it[1]);
}
if(K == 1) {
if(mxl <= mnr && mxd <= mnu) return {{mxl, mxd}};
return EMP;
}
if(K == 2) {
vvi B; vpi S;
for(auto y: {mxd, mnu}) {
B = rem(A, mxl, y);
S = sol(B, 1);
if(S.size()) return {{mxl, y}, S[0]};
}
return EMP;
}
if(K == 3) {
vvi B; vpi S;
for(auto x: {mxl, mnr}) for(auto y: {mxd, mnu}) {
B = rem(A, x, y);
S = sol(B, 2);
if(S.size()) return {{x, y}, S[0], S[1]};
}
return EMP;
}
if(K == 4) {
vvi B; vpi S;
for(auto x: {mxl, mnr}) for(auto y: {mxd, mnu}) {
B = rem(A, x, y);
S = sol(B, 3);
if(S.size()) return {{x, y}, S[0], S[1], S[2]};
}
S = sol4(A);
if(S.size()) return S;
for(auto& it: A) it = {XS - it[2] + 1, it[1], XS - it[0] + 1, it[3]};
S = sol4(A);
if(S.size()) {
for(auto& [x, y]: S) x = XS - x + 1;
return S;
}
return EMP;
}
}
int main() {
vvi A;
int N, K; scanf("%d%d", &N, &K);
for(int i=0; i<N; i++) {
vi H(4);
for(int j=0; j<4; j++) scanf("%d", &H[j]);
A.push_back(H);
X.push_back(H[0]);
X.push_back(H[2]);
Y.push_back(H[1]);
Y.push_back(H[3]);
}
sort(X.begin(), X.end()); X.resize(unique(X.begin(), X.end()) - X.begin()); XS = X.size();
sort(Y.begin(), Y.end()); Y.resize(unique(Y.begin(), Y.end()) - Y.begin()); YS = Y.size();
for(auto& it: A) {
it[0] = f(X, it[0]);
it[1] = f(Y, it[1]);
it[2] = f(X, it[2]);
it[3] = f(Y, it[3]);
}
vpi ans;
for(int k=1; k<=K && ans.empty(); k++) ans = sol(A, K);
assert(!ans.empty());
while((int)ans.size() < K) ans.push_back({1, 1});
for(auto& [x, y]: ans) printf("%d %d\n", X[x-1], Y[y-1]);
return 0;
}
Compilation message (stderr)
hamburg.cpp: In function 'vpi sol(vvi&, int)':
hamburg.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
137 | }
| ^
hamburg.cpp: In function 'int main()':
hamburg.cpp:141:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | int N, K; scanf("%d%d", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:144:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | for(int j=0; j<4; j++) scanf("%d", &H[j]);
| ~~~~~^~~~~~~~~~~~~
# | 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... |