This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define trav(x,a) for (auto& x: a)
#define sz(x) (int)(x).size()
#define mem(a,v) memset((a), (v), sizeof (a))
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int _i = 0; _i < (n); _i++) ni(a[_i])
#define nal(a, n) for (int _i = 0; _i < (n); _i++) nl(a[_i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define ar array<int,4>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
const int N = 2e5 + 5;
const double eps = 1e-9;
bool ok(ar j, ar i) {
return !(j[2] < i[0] || i[2] < j[0] || j[3] < i[1] || i[3] < j[1]);
}
bool ins(ar j, pii i) {
return j[0] <= i.st && i.st <= j[2] && j[1] <= i.nd && i.nd <= j[3];
}
bool val(ar i) {
return i[0] <= i[2] && i[1] <= i[3];
}
vii check(vector<ar>& a, int k, pii ed);
vii solve1(vector<ar>& a) {
int n = sz(a)-1;
pii U, L, R, D;
U = R = {inf, -1};
D = L = {-inf, -1};
for (int i = 1; i <= n; i++) {
U = min(U, {a[i][3], i});
D = max(D, {a[i][1], i});
L = max(L, {a[i][0], i});
R = min(R, {a[i][2], i});
}
if (val({L.st, D.st, R.st, U.st}))
return {{L.st, D.st}};
return {};
}
vii solve2(vector<ar>& a) {
int n = sz(a)-1;
pii U, L, R, D;
U = R = {inf, -1};
D = L = {-inf, -1};
for (int i = 1; i <= n; i++) {
U = min(U, {a[i][3], i});
D = max(D, {a[i][1], i});
L = max(L, {a[i][0], i});
R = min(R, {a[i][2], i});
}
vii ans;
ans = check(a, 1, mp(R.st, U.st));
if (!ans.empty()) return ans;
ans = check(a, 1, mp(R.st, D.st));
if (!ans.empty()) return ans;
ans = check(a, 1, mp(L.st, U.st));
if (!ans.empty()) return ans;
ans = check(a, 1, mp(L.st, D.st));
if (!ans.empty()) return ans;
return {};
}
vii solve3(vector<ar>& a) {
int n = sz(a)-1;
pii U, L, R, D;
U = R = {inf, -1};
D = L = {-inf, -1};
for (int i = 1; i <= n; i++) {
U = min(U, {a[i][3], i});
D = max(D, {a[i][1], i});
L = max(L, {a[i][0], i});
R = min(R, {a[i][2], i});
}
vii ans;
ans = check(a, 2, mp(R.st, U.st));
if (!ans.empty()) return ans;
ans = check(a, 2, mp(R.st, D.st));
if (!ans.empty()) return ans;
ans = check(a, 2, mp(L.st, U.st));
if (!ans.empty()) return ans;
ans = check(a, 2, mp(L.st, D.st));
if (!ans.empty()) return ans;
return {};
}
int crossV(ar i, int j) {
return i[0] <= j && j <= i[2];
}
int crossH(ar i, int j) {
return i[1] <= j && j <= i[3];
}
vii solve4(vector<ar>& a) {
int n = sz(a)-1;
pii U, L, R, D;
U = R = {inf, -1};
D = L = {-inf, -1};
for (int i = 1; i <= n; i++) {
U = min(U, {a[i][3], i});
D = max(D, {a[i][1], i});
L = max(L, {a[i][0], i});
R = min(R, {a[i][2], i});
}
vii ans;
ans = check(a, 3, mp(R.st, U.st));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(R.st, D.st));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(L.st, U.st));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(L.st, D.st));
if (!ans.empty()) return ans;
ar lo, hi;
for (int i = 0; i < 4; i++)
lo[i] = inf, hi[i] = -inf;
for (int i = 1; i <= n; i++) {
int msk = (crossV(a[i], R.st) << 3) + (crossH(a[i], U.st) << 2) + (crossV(a[i], L.st) << 1) + (crossH(a[i], D.st) << 0);
if (__builtin_popcount(msk) != 1)
continue;
int b = 0;
if (msk & 1) b = 0; // D
if (msk & 2) b = 1; // L
if (msk & 4) b = 2; // U
if (msk & 8) b = 3; // R
lo[b] = min(lo[b], a[i][2 + (b & 1)]);
hi[b] = max(hi[b], a[i][0 + (b & 1)]);
}
ans = check(a, 3, mp(R.st, lo[3]));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(R.st, hi[3]));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(L.st, lo[1]));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(L.st, hi[1]));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(lo[0], D.st));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(hi[0], D.st));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(lo[2], U.st));
if (!ans.empty()) return ans;
ans = check(a, 3, mp(hi[2], U.st));
if (!ans.empty()) return ans;
return {};
}
vii check(vector<ar>& a, int k, pii ed) {
int n = sz(a)-1;
if (n <= k) {
vii ret;
for (int i = 1; i <= k; i++)
ret.pb({a[i][0], a[i][1]});
return ret;
}
vector<ar> nx; nx.pb({0, 0, 0, 0});
for (int i = 1; i <= n; i++)
if (!ins(a[i], ed))
nx.pb(a[i]);
vii tmp;
if (k == 1)
tmp = solve1(nx);
else if (k == 2)
tmp = solve2(nx);
else
tmp = solve3(nx);
if (!tmp.empty())
tmp.pb(ed);
return tmp;
}
int main() {
int n, k; scanf("%d %d", &n, &k);
vector<ar> a(n+1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 4; j++)
scanf("%d", &a[i][j]);
}
if (n <= k) {
for (int i = 1; i <= n; i++)
printf("%d %d\n", a[i][0], a[i][1]);
for (int i = n+1; i <= k; i++)
printf("1 1\n");
return 0;
}
{
vii ans = solve1(a);
if (!ans.empty()) {
while (sz(ans) < k) ans.pb({1, 1});
trav(x, ans) printf("%d %d\n", x.st, x.nd);
return 0;
}
}
{
vii ans = solve2(a);
if (!ans.empty()) {
while (sz(ans) < k) ans.pb({1, 1});
trav(x, ans) printf("%d %d\n", x.st, x.nd);
return 0;
}
}
{
vii ans = solve3(a);
if (!ans.empty()) {
while (sz(ans) < k) ans.pb({1, 1});
trav(x, ans) printf("%d %d\n", x.st, x.nd);
return 0;
}
}
{
vii ans = solve4(a);
if (!ans.empty()) {
while (sz(ans) < k) ans.pb({1, 1});
trav(x, ans) printf("%d %d\n", x.st, x.nd);
return 0;
}
}
return 0;
}
Compilation message (stderr)
hamburg.cpp: In function 'int main()':
hamburg.cpp:200:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
200 | int n, k; scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
hamburg.cpp:204:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
204 | scanf("%d", &a[i][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... |