oj.uz

Submission #484456

# Submission time Handle Problem Language Result Execution time Memory
484456 2021-11-03T14:02:49 Z valerikk Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 356 ms 53680 KB 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int INF = 1'000'000'000;
const int N = 800005;


struct Point {
	int x, y;
};

struct Seg {
	int l, r;

	Seg() : l(1), r(N) {}

	Seg(int l, int r) : l(l), r(r) {}
};

void self_intersect(Seg &a, const Seg &b) {
	a.l = max(a.l, b.l);
	a.r = min(a.r, b.r);
}

Seg intersect(Seg a, const Seg &b) {
	self_intersect(a, b);
	return a;
}

bool inside(int x, const Seg &s) {
	return x >= s.l && x <= s.r;
}

struct Rect {
	Seg x, y;

	Rect() : x{}, y{} {}

	Rect(const Seg &x, const Seg &y) : x(x), y(y) {}
};

istream &operator>>(istream &stream, Rect &r) {
	stream >> r.x.l >> r.y.l >> r.x.r >> r.y.r;
	return stream;
}

void self_intersect(Rect &a, const Rect &b) {
	self_intersect(a.x, b.x);
	self_intersect(a.y, b.y);
}

Rect intersect(Rect a, const Rect &b) {
	self_intersect(a, b);
	return a;
}

bool inside(const Point &p, const Rect &r) {
	return inside(p.x, r.x) && inside(p.y, r.y);
}

int k;
vector<int> vals;

void adjust(int &val) {
	val = lower_bound(vals.begin(), vals.end(), val) - vals.begin();
}

void output(const vector<Point> &pts) {
	for (const auto &[x, y] : pts) {
		cout << vals[x] << " " << vals[y] << "\n";
	}
	exit(0);
}

void solve(const vector<Rect> &rects, const vector<Point> &pts) {
	if ((int)pts.size() == k) {
		if (rects.empty()) {
			output(pts);
		}

		return;
	}

	Rect intersection;
	for (const auto &rect : rects) {
		self_intersect(intersection, rect);
	}

	for (int x : {intersection.x.l, intersection.x.r}) {
		for (int y : {intersection.y.l, intersection.y.r}) {
			Point p = {x, y};
			
			auto npts = pts;
			npts.push_back(p);
			
			vector<Rect> nrects;
			for (const auto &rect : rects) {
				if (!inside(p, rect)) {
					nrects.push_back(rect);
				}
			}

			solve(nrects, npts);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n >> k;
	vector<Rect> rects(n);
	for (auto &r : rects) {
		cin >> r;
	}

	vals.push_back(0);
	vals.push_back(INF + 1);
	for (const auto &r : rects) {
		vals.push_back(r.x.l);
		vals.push_back(r.x.r);
		vals.push_back(r.y.l);
		vals.push_back(r.y.r);
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	while (vals.size() <= N) {
		vals.back() = INF;
		vals.push_back(INF + 1);
	}


	for (auto &r : rects) {
		adjust(r.x.l);
		adjust(r.y.l);
		adjust(r.x.r);
		adjust(r.y.r);
	}

	solve(rects, vector<Point>{});

	Rect intersection;
	for (const auto &r : rects) {
		self_intersect(intersection, r);
	}

	int dy = intersection.y.r, uy = intersection.y.l;
	int lx = intersection.x.r, rx = intersection.x.l;

	Seg base_sd = {lx + 1, rx - 1}, base_su = {lx + 1, rx - 1};
	Seg base_sl = {dy + 1, uy - 1}, base_sr = {dy + 1, uy - 1};

	vector<Seg> pref_dl(N + 1);
	vector<Seg> suff_dr(N + 1);
	vector<Seg> pref_du(N + 1);
	vector<Seg> suff_du(N + 1);
	vector<Seg> pref_lr(N + 1);
	vector<Seg> suff_lr(N + 1);
	vector<Seg> suff_lu(N + 1);
	vector<Seg> suff_ru(N + 1);

	for (const auto &r : rects) {
		int fd = inside(dy, r.y);
		int fu = inside(uy, r.y);
		int fl = inside(lx, r.x);
		int fr = inside(rx, r.x);
		
		if (fd + fu + fl + fr > 2) {
			continue;
		}

		if (fd + fu + fl + fr == 0) {
			assert(0);
		}

		if (fd + fu + fl + fr == 1) {
			if (fd) {
				self_intersect(base_sd, r.x);
			} else if (fu) {
				self_intersect(base_su, r.x);
			} else if (fl) {
				self_intersect(base_sl, r.y);
			} else {
				self_intersect(base_sr, r.y);
			}
		} else {
			if (fd && fu) {
				self_intersect(pref_du[r.x.r], r.x);
				self_intersect(suff_du[r.x.l], r.x);
			} else if (fd && fl) {
				self_intersect(pref_dl[r.x.r], r.y);
			} else if (fd && fr) {
				self_intersect(suff_dr[r.x.l], r.y);
			} else if (fl && fr) {
				self_intersect(pref_lr[r.y.r], r.y);
				self_intersect(suff_lr[r.y.l], r.y);
			} else if (fu && fl) {
				self_intersect(suff_lu[r.y.r], r.x);
			} else {
				self_intersect(suff_ru[r.y.r], r.x);
			}
		}
	}

	for (int i = 0; i < N; ++i) {
		self_intersect(pref_lr[i + 1], pref_lr[i]);
		self_intersect(pref_dl[i + 1], pref_dl[i]);
		self_intersect(pref_du[i + 1], pref_du[i]);
	}
	for (int i = N; i > 0; --i) {
		self_intersect(suff_dr[i - 1], suff_dr[i]);
		self_intersect(suff_du[i - 1], suff_du[i]);
		self_intersect(suff_lu[i - 1], suff_lu[i]);
		self_intersect(suff_ru[i - 1], suff_ru[i]);
		self_intersect(suff_lr[i - 1], suff_lr[i]);
	}

	for (int dx = base_sd.l; dx <= base_sd.r; ++dx) {
		Seg su = base_su, sl = base_sl, sr = base_sr;

		self_intersect(sl, pref_dl[dx - 1]);
		self_intersect(sr, suff_dr[dx + 1]);
		self_intersect(su, pref_du[dx - 1]);
		self_intersect(su, suff_du[dx + 1]);

		int ly = pref_lr[N].r;

		if (!inside(ly, sl)) {
			continue;
		}

		self_intersect(sr, pref_lr[ly - 1]);
		self_intersect(sr, suff_lr[ly + 1]);

		if (sr.l > sr.r) {
			continue;
		}

		int ry = sr.r;

		self_intersect(su, suff_lu[ly + 1]);
		self_intersect(su, suff_ru[ry + 1]);

		if (su.l > su.r) {
			continue;
		}

		int ux = su.l;


		output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}});
	}

	for (int dx = base_sd.l; dx <= base_sd.r; ++dx) {
		Seg su = base_su, sl = base_sl, sr = base_sr;
			
		self_intersect(sl, pref_dl[dx - 1]);
		self_intersect(sr, suff_dr[dx + 1]);
		self_intersect(su, pref_du[dx - 1]);
		self_intersect(su, suff_du[dx + 1]);

		int ry = pref_lr[N].r;
		
		if (!inside(ry, sr)) {
			continue;
		}

		self_intersect(sl, pref_lr[ry - 1]);
		self_intersect(sl, suff_lr[ry + 1]);

		if (sl.l > sl.r) {
			continue;
		}

		int ly = sl.r;

		self_intersect(su, suff_lu[ly + 1]);
		self_intersect(su, suff_ru[ry + 1]);

		if (su.l > su.r) {
			continue;
		}

		int ux = su.l;
		
		output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}});
	}


	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4544 KB Output is correct
2 Correct 6 ms 4544 KB Output is correct
3 Correct 6 ms 4544 KB Output is correct
4 Correct 5 ms 4544 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4500 KB Output is correct
2 Correct 6 ms 4544 KB Output is correct
3 Correct 7 ms 4576 KB Output is correct
4 Correct 5 ms 4544 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4544 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 7 ms 4544 KB Output is correct
4 Correct 6 ms 4540 KB Output is correct
5 Correct 5 ms 4524 KB Output is correct
6 Correct 6 ms 4544 KB Output is correct
7 Correct 6 ms 4544 KB Output is correct
8 Correct 6 ms 4544 KB Output is correct
9 Correct 6 ms 4576 KB Output is correct
10 Correct 7 ms 4544 KB Output is correct
11 Correct 7 ms 4544 KB Output is correct
12 Correct 6 ms 4544 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4544 KB Output is correct
2 Correct 8 ms 4544 KB Output is correct
3 Correct 7 ms 4544 KB Output is correct
4 Correct 6 ms 4544 KB Output is correct
5 Correct 6 ms 4544 KB Output is correct
6 Correct 6 ms 4544 KB Output is correct
7 Correct 6 ms 4544 KB Output is correct
8 Correct 7 ms 4544 KB Output is correct
9 Correct 6 ms 4548 KB Output is correct
10 Correct 7 ms 4544 KB Output is correct
11 Correct 8 ms 4544 KB Output is correct
12 Correct 6 ms 4544 KB Output is correct
13 Correct 6 ms 4576 KB Output is correct
14 Incorrect 41 ms 53680 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4544 KB Output is correct
2 Correct 6 ms 4544 KB Output is correct
3 Correct 6 ms 4544 KB Output is correct
4 Correct 5 ms 4544 KB Output is correct
5 Correct 263 ms 7652 KB Output is correct
6 Correct 269 ms 7612 KB Output is correct
7 Correct 265 ms 7656 KB Output is correct
8 Correct 259 ms 7612 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4500 KB Output is correct
2 Correct 6 ms 4544 KB Output is correct
3 Correct 7 ms 4576 KB Output is correct
4 Correct 5 ms 4544 KB Output is correct
5 Correct 285 ms 10304 KB Output is correct
6 Correct 270 ms 13112 KB Output is correct
7 Correct 271 ms 9956 KB Output is correct
8 Correct 279 ms 15160 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4544 KB Output is correct
2 Correct 6 ms 4556 KB Output is correct
3 Correct 7 ms 4544 KB Output is correct
4 Correct 6 ms 4540 KB Output is correct
5 Correct 5 ms 4524 KB Output is correct
6 Correct 6 ms 4544 KB Output is correct
7 Correct 6 ms 4544 KB Output is correct
8 Correct 6 ms 4544 KB Output is correct
9 Correct 6 ms 4576 KB Output is correct
10 Correct 7 ms 4544 KB Output is correct
11 Correct 7 ms 4544 KB Output is correct
12 Correct 6 ms 4544 KB Output is correct
13 Correct 266 ms 10968 KB Output is correct
14 Correct 276 ms 10420 KB Output is correct
15 Correct 263 ms 11316 KB Output is correct
16 Correct 266 ms 9648 KB Output is correct
17 Correct 265 ms 10428 KB Output is correct
18 Correct 265 ms 8500 KB Output is correct
19 Correct 284 ms 12640 KB Output is correct
20 Correct 356 ms 18076 KB Output is correct
21 Correct 277 ms 12728 KB Output is correct
22 Correct 299 ms 17852 KB Output is correct
23 Correct 318 ms 17640 KB Output is correct
24 Correct 317 ms 17124 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4544 KB Output is correct
2 Correct 8 ms 4544 KB Output is correct
3 Correct 7 ms 4544 KB Output is correct
4 Correct 6 ms 4544 KB Output is correct
5 Correct 6 ms 4544 KB Output is correct
6 Correct 6 ms 4544 KB Output is correct
7 Correct 6 ms 4544 KB Output is correct
8 Correct 7 ms 4544 KB Output is correct
9 Correct 6 ms 4548 KB Output is correct
10 Correct 7 ms 4544 KB Output is correct
11 Correct 8 ms 4544 KB Output is correct
12 Correct 6 ms 4544 KB Output is correct
13 Correct 6 ms 4576 KB Output is correct
14 Incorrect 41 ms 53680 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -