Submission #218033

#	Time	Username	Problem	Language	Result	Execution time	Memory
218033		atoiz	Hamburg Steak (JOI20_hamburg)	C++14	100 / 100	1095 ms	35868 KiB

hamburg

/*input
6 4
5 1 8 9
1 2 4 8
2 10 5 10
9 2 10 4
1 1 10 1
5 3 5 10

*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#include <functional>

using namespace std;

const int INF = 1e9 + 8;
void minimize(int &x, int y) { x = (x < y ? x : y); }
void maximize(int &x, int y) { x = (x > y ? x : y); }

struct Rect { int x1, x2, y1, y2; };

vector<pair<int, int>> skewers;

bool contain(Rect r, int x, int y)
{
	return (x >= r.x1 && r.x2 >= x && y >= r.y1 && r.y2 >= y);
}

vector<Rect> cut(vector<Rect> rects, int x, int y)
{
	vector<Rect> leftover;
	for (auto r : rects) {
		if (!contain(r, x, y)) {
			leftover.push_back(r);
		}
	}
	return leftover;
}

bool solve(vector<Rect> rects, int K)
{
	if (rects.empty()) return true;
	if (K == 0) return false;

	int lim_x1 = INF, lim_x2 = 0, lim_y1 = INF, lim_y2 = 0;
	for (auto &r : rects) {
		minimize(lim_x1, r.x2);
		maximize(lim_x2, r.x1);
		minimize(lim_y1, r.y2);
		maximize(lim_y2, r.y1);
	}

	skewers.emplace_back(lim_x1, lim_y1);
	if (solve(cut(rects, lim_x1, lim_y1), K - 1)) return true;
	skewers.pop_back();

	skewers.emplace_back(lim_x2, lim_y1);
	if (solve(cut(rects, lim_x2, lim_y1), K - 1)) return true;
	skewers.pop_back();

	skewers.emplace_back(lim_x1, lim_y2);
	if (solve(cut(rects, lim_x1, lim_y2), K - 1)) return true;
	skewers.pop_back();

	skewers.emplace_back(lim_x2, lim_y2);
	if (solve(cut(rects, lim_x2, lim_y2), K - 1)) return true;
	skewers.pop_back();

	if (K != 4) return false;

	assert(lim_x1 < lim_x2);
	assert(lim_y1 < lim_y2);

	// solve 4-sides
	map<string, vector<pair<int, int>>> intervals;
	int l_x1 = 0, l_x2 = 0, l_y1 = 0, l_y2 = 0;
	int r_x1 = INF, r_x2 = INF, r_y1 = INF, r_y2 = INF;

	for (auto &r : rects) {
		maximize(r.x1, lim_x1);
		minimize(r.x2, lim_x2);
		maximize(r.y1, lim_y1);
		minimize(r.y2, lim_y2);

		string sides = "";
		if (r.x1 == lim_x1) sides += 'L';
		if (r.x2 == lim_x2) sides += 'R';
		if (r.y1 == lim_y1) sides += 'D';
		if (r.y2 == lim_y2) sides += 'U';

		assert(!sides.empty());
		if ((int) sides.size() > 2) continue;

		if (sides == "LR") intervals[sides].emplace_back(r.y1, r.y2);
		else if (sides == "DU") intervals[sides].emplace_back(r.x1, r.x2);
		else if (sides == "L") maximize(l_x1, r.y1), minimize(r_x1, r.y2);
		else if (sides == "R") maximize(l_x2, r.y1), minimize(r_x2, r.y2);
		else if (sides == "D") maximize(l_y1, r.x1), minimize(r_y1, r.x2);
		else if (sides == "U") maximize(l_y2, r.x1), minimize(r_y2, r.x2);
		else if (sides == "LD") intervals[sides].emplace_back(r.x2, r.y2);
		else if (sides == "RD") intervals[sides].emplace_back(r.x1, r.y2);
		else if (sides == "LU") intervals[sides].emplace_back(r.x2, r.y1);
		else if (sides == "RU") intervals[sides].emplace_back(r.x1, r.y1);
		else assert(false);
	}
	assert(l_x1 <= r_x1), assert(l_x2 <= r_x2);
	assert(l_y1 <= r_y1), assert(l_y2 <= r_y2);

	// identify important points
	vector<int> pnts_l, pnts_d, pnts_u, pnts_r;
	pnts_l.push_back(l_x1), pnts_l.push_back(r_x1);
	pnts_r.push_back(l_x2), pnts_r.push_back(r_x2);
	pnts_d.push_back(l_y1), pnts_d.push_back(r_y1);
	pnts_u.push_back(l_y2), pnts_u.push_back(r_y2);
	for (auto p : intervals["LD"]) pnts_l.push_back(p.second), pnts_d.push_back(p.first);
	for (auto p : intervals["RD"]) pnts_r.push_back(p.second), pnts_d.push_back(p.first);
	for (auto p : intervals["LU"]) pnts_l.push_back(p.second), pnts_u.push_back(p.first);
	for (auto p : intervals["RU"]) pnts_r.push_back(p.second), pnts_u.push_back(p.first);
	for (auto p : intervals["LR"]) pnts_l.push_back(p.first), pnts_r.push_back(p.first), pnts_l.push_back(p.second), pnts_r.push_back(p.second);
	for (auto p : intervals["DU"]) pnts_d.push_back(p.first), pnts_u.push_back(p.first), pnts_d.push_back(p.second), pnts_u.push_back(p.second);
	sort(pnts_l.begin(), pnts_l.end());
	sort(pnts_r.begin(), pnts_r.end());
	sort(pnts_d.begin(), pnts_d.end());
	sort(pnts_u.begin(), pnts_u.end());
	pnts_l.erase(unique(pnts_l.begin(), pnts_l.end()), pnts_l.end());
	pnts_r.erase(unique(pnts_r.begin(), pnts_r.end()), pnts_r.end());
	pnts_d.erase(unique(pnts_d.begin(), pnts_d.end()), pnts_d.end());
	pnts_u.erase(unique(pnts_u.begin(), pnts_u.end()), pnts_u.end());

	auto get_pos = [&](vector<int> &vec, int x) -> int { return int(lower_bound(vec.begin(), vec.end(), x) - vec.begin()); };

	// identify range (corner)
	vector<int> range_dl(pnts_d.size(), pnts_l.back()), range_dr(pnts_d.size(), pnts_r.back());
	vector<int> range_lu(pnts_l.size(), pnts_u.back()), range_ru(pnts_r.size(), pnts_u.front());

	for (auto p : intervals["LD"]) minimize(range_dl[get_pos(pnts_d, p.first)], p.second);
	for (auto p : intervals["RD"]) minimize(range_dr[get_pos(pnts_d, p.first)], p.second);
	for (auto p : intervals["LU"]) minimize(range_lu[get_pos(pnts_l, p.second)], p.first);
	for (auto p : intervals["RU"]) maximize(range_ru[get_pos(pnts_r, p.second)], p.first);

	for (int i = 1; i < (int) pnts_d.size(); ++i) minimize(range_dl[i], range_dl[i - 1]);
	for (int i = (int) pnts_d.size() - 2; i >= 0; --i) minimize(range_dr[i], range_dr[i + 1]);
	for (int i = (int) pnts_l.size() - 2; i >= 0; --i) minimize(range_lu[i], range_lu[i + 1]);
	for (int i = (int) pnts_r.size() - 2; i >= 0; --i) maximize(range_ru[i], range_ru[i + 1]);

	// identify range (edges)
	for (string sides : {"LR", "DU"}) {
		vector<pair<int, int>> &vec = intervals[sides];
		sort(vec.begin(), vec.end());
		vector<pair<int, int>> tmp;
		tmp.swap(vec);
		for (auto &p : tmp) {
			while (!vec.empty() && vec.back().second >= p.second) vec.pop_back();
			if (vec.empty() || vec.back().first < p.first) vec.push_back(p);
		}
		// for (auto p : vec) cout << sides << ": " << p.first << ' ' << p.second << endl;
	}

	// check skewer locations
	// auto comp_by_second = [&](pair<int, int> &lhs, pair<int, int> &rhs) -> bool {
	// 	return (lhs.second == rhs.second ? lhs.first < rhs.first : lhs.second < rhs.second);
	// };
	auto check_du = [&](int x_d, int y_l, int y_r) -> bool {
		if (y_l < l_x1) return false;
		if (y_r < l_x2) return false;

		int id_l = get_pos(pnts_l, y_l), id_r = get_pos(pnts_r, y_r);
		int x1_u = (id_r + 1 != (int) pnts_r.size() ? range_ru[id_r + 1] : pnts_u.front());
		int x2_u = (id_l + 1 != (int) pnts_l.size() ? range_lu[id_l + 1] : pnts_u.back());
		// cout << x1_u << ' ' << x2_u << endl;
		maximize(x1_u, l_y2), minimize(x2_u, r_y2);
		// cout << x1_u << ' ' << x2_u << endl;
		if (x1_u > x2_u) return false;

		if (intervals["DU"].empty()) return true;
		if (x_d <= intervals["DU"].front().second && x_d >= intervals["DU"].back().first) return true;
		if (x_d <= intervals["DU"].front().second) {
			int lim1_u = max(x1_u, intervals["DU"].back().first);
			int lim2_u = min(x2_u, intervals["DU"].back().second);
			if (lim1_u <= lim2_u) {
				auto it = upper_bound(intervals["DU"].begin(), intervals["DU"].end(), make_pair(x_d, INF));
				if (it == intervals["DU"].end() || lim1_u <= it->second) return true;
			}
		}

		if (x_d >= intervals["DU"].back().first) {
			int lim1_u = max(x1_u, intervals["DU"].front().first);
			int lim2_u = min(x2_u, intervals["DU"].front().second);
			if (lim1_u <= lim2_u) {
				auto it = upper_bound(intervals["DU"].begin(), intervals["DU"].end(), make_pair(lim2_u, INF));
				if (it == intervals["DU"].end() || x_d <= it->second) return true;
			}
		}

		return false;
	};
	for (int x_d : pnts_d) if (l_y1 <= x_d && r_y1 >= x_d) {
		int id = get_pos(pnts_d, x_d);
		int y_l = (id ? range_dl[id - 1] : pnts_l.back());
		int y_r = (id + 1 != (int) pnts_d.size() ? range_dr[id + 1] : pnts_r.back());
		minimize(y_l, r_x1), minimize(y_r, r_x2);

		// empty
		if (intervals["LR"].empty()) {
			if (check_du(x_d, y_l, y_r)) {
				skewers.emplace_back(x_d, lim_y1);
				return solve(cut(rects, x_d, lim_y1), K - 1);
			}
			continue;
		}

		// prefix-suffix
		{
			bool valid = true;
			int lim_l = min(y_l, intervals["LR"].front().second), lim_r = y_r;
			auto it = upper_bound(intervals["LR"].begin(), intervals["LR"].end(), make_pair(lim_l, INF));

			if (it != intervals["LR"].end()) {
				minimize(lim_r, it->second);
				if (lim_r < intervals["LR"].back().first) valid = false;
			}
			// if (valid) cout << "pref-suff: " << x_d << ": " << lim_l << ' ' << lim_r << endl;
			if (valid && check_du(x_d, lim_l, lim_r)) {
				skewers.emplace_back(x_d, lim_y1);
				return solve(cut(rects, x_d, lim_y1), K - 1);
			}
		}

		// suffix-prefix
		{
			bool valid = true;
			int lim_l = y_l, lim_r = min(y_r, intervals["LR"][0].second);
			auto it = upper_bound(intervals["LR"].begin(), intervals["LR"].end(), make_pair(lim_r, INF));

			if (it != intervals["LR"].end()) {
				minimize(lim_l, it->second);
				if (lim_l < intervals["LR"].back().first) valid = false;
			}

			// if (valid) cout << "suff-pref: " << x_d << ": " << lim_l << ' ' << lim_r << endl;
			if (valid && check_du(x_d, lim_l, lim_r)) {
				skewers.emplace_back(x_d, lim_y1);
				return solve(cut(rects, x_d, lim_y1), K - 1);
			}
		}
	}

	assert(false);
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int N, K;
	cin >> N >> K;
	vector<Rect> rects(N);
	for (auto &r : rects) cin >> r.x1 >> r.y1 >> r.x2 >> r.y2;
	assert(solve(rects, K));
	while ((int) skewers.size() < K) skewers.push_back(skewers.back());
	for (auto &p : skewers) cout << p.first << ' ' << p.second << '\n';

}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79