oj.uz

Submission #484454

# Submission time Handle Problem Language Result Execution time Memory
484454 2021-11-03T13:55:54 Z valerikk Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 365 ms 53692 KB 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

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


struct Point {
	int x, y;
};

struct Seg {
	int l, r;

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

	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() <= MAX) {
		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, base_su, base_sl, base_sr;

	vector<Seg> pref_dl(MAX + 1);
	vector<Seg> suff_dr(MAX + 1);
	vector<Seg> pref_du(MAX + 1);
	vector<Seg> suff_du(MAX + 1);
	vector<Seg> pref_lr(MAX + 1);
	vector<Seg> suff_lr(MAX + 1);
	vector<Seg> suff_lu(MAX + 1);
	vector<Seg> suff_ru(MAX + 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 < MAX; ++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 = MAX; 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[MAX].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[MAX].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 6 ms 4544 KB Output is correct
2 Correct 5 ms 4544 KB Output is correct
3 Correct 6 ms 4544 KB Output is correct
4 Correct 6 ms 4572 KB Output is correct

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4552 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 4540 KB Output is correct
5 Correct 6 ms 4544 KB Output is correct
6 Correct 5 ms 4544 KB Output is correct
7 Correct 6 ms 4544 KB Output is correct
8 Correct 6 ms 4584 KB Output is correct
9 Correct 6 ms 4544 KB Output is correct
10 Correct 6 ms 4544 KB Output is correct
11 Correct 6 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 5 ms 4544 KB Output is correct
3 Correct 5 ms 4544 KB Output is correct
4 Correct 7 ms 4564 KB Output is correct
5 Correct 7 ms 4544 KB Output is correct
6 Correct 6 ms 4544 KB Output is correct
7 Correct 8 ms 4544 KB Output is correct
8 Correct 8 ms 4544 KB Output is correct
9 Correct 7 ms 4556 KB Output is correct
10 Correct 9 ms 4612 KB Output is correct
11 Correct 8 ms 4544 KB Output is correct
12 Correct 7 ms 4544 KB Output is correct
13 Correct 6 ms 4576 KB Output is correct
14 Incorrect 40 ms 53692 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 6 ms 4544 KB Output is correct
2 Correct 5 ms 4544 KB Output is correct
3 Correct 6 ms 4544 KB Output is correct
4 Correct 6 ms 4572 KB Output is correct
5 Correct 268 ms 7712 KB Output is correct
6 Correct 295 ms 7752 KB Output is correct
7 Correct 266 ms 7740 KB Output is correct
8 Correct 265 ms 7736 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4544 KB Output is correct
2 Correct 6 ms 4572 KB Output is correct
3 Correct 6 ms 4544 KB Output is correct
4 Correct 6 ms 4544 KB Output is correct
5 Correct 266 ms 10288 KB Output is correct
6 Correct 287 ms 13356 KB Output is correct
7 Correct 269 ms 9908 KB Output is correct
8 Correct 290 ms 14960 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4552 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 4540 KB Output is correct
5 Correct 6 ms 4544 KB Output is correct
6 Correct 5 ms 4544 KB Output is correct
7 Correct 6 ms 4544 KB Output is correct
8 Correct 6 ms 4584 KB Output is correct
9 Correct 6 ms 4544 KB Output is correct
10 Correct 6 ms 4544 KB Output is correct
11 Correct 6 ms 4544 KB Output is correct
12 Correct 6 ms 4544 KB Output is correct
13 Correct 273 ms 10924 KB Output is correct
14 Correct 273 ms 10352 KB Output is correct
15 Correct 315 ms 11316 KB Output is correct
16 Correct 275 ms 9576 KB Output is correct
17 Correct 276 ms 10552 KB Output is correct
18 Correct 297 ms 8500 KB Output is correct
19 Correct 274 ms 12832 KB Output is correct
20 Correct 365 ms 18068 KB Output is correct
21 Correct 294 ms 12724 KB Output is correct
22 Correct 297 ms 17892 KB Output is correct
23 Correct 316 ms 17600 KB Output is correct
24 Correct 314 ms 17216 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 5 ms 4544 KB Output is correct
3 Correct 5 ms 4544 KB Output is correct
4 Correct 7 ms 4564 KB Output is correct
5 Correct 7 ms 4544 KB Output is correct
6 Correct 6 ms 4544 KB Output is correct
7 Correct 8 ms 4544 KB Output is correct
8 Correct 8 ms 4544 KB Output is correct
9 Correct 7 ms 4556 KB Output is correct
10 Correct 9 ms 4612 KB Output is correct
11 Correct 8 ms 4544 KB Output is correct
12 Correct 7 ms 4544 KB Output is correct
13 Correct 6 ms 4576 KB Output is correct
14 Incorrect 40 ms 53692 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -