oj.uz

Submission #217961

# Submission time Handle Problem Language Result Execution time Memory
217961 2020-03-31T10:49:09 Z atoiz Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 302 ms 29168 KB 
/*input
3 3
1 1 1 1
1 2 1 2
1 3 1 3
*/

#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];
		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);
		}
	}

	// 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 x1_u = range_ru[get_pos(pnts_r, y_r)];
		int x2_u = range_lu[get_pos(pnts_l, y_l)];
		maximize(x1_u, l_y2), minimize(x2_u, r_y2);
		if (x1_u > x2_u) return false;

		if (intervals["DU"].empty()) 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 y_l = range_dl[get_pos(pnts_d, x_d)];
		int y_r = range_dr[get_pos(pnts_d, x_d)];
		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"][0].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 && 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 && 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.0 / 1.0

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

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 544 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Correct 3 ms 548 KB Output is correct
12 Correct 2 ms 640 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 704 KB Output is correct
15 Correct 5 ms 668 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Runtime error 6 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 99 ms 9668 KB Output is correct
6 Correct 100 ms 9720 KB Output is correct
7 Correct 102 ms 9668 KB Output is correct
8 Correct 111 ms 9720 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 2 ms 544 KB Output is correct
5 Correct 108 ms 12268 KB Output is correct
6 Correct 146 ms 11688 KB Output is correct
7 Correct 108 ms 12268 KB Output is correct
8 Correct 131 ms 20840 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 544 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 628 KB Output is correct
11 Correct 3 ms 548 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 111 ms 13168 KB Output is correct
14 Correct 118 ms 13372 KB Output is correct
15 Correct 127 ms 12016 KB Output is correct
16 Correct 118 ms 12144 KB Output is correct
17 Correct 114 ms 14572 KB Output is correct
18 Correct 103 ms 12100 KB Output is correct
19 Correct 111 ms 15084 KB Output is correct
20 Correct 119 ms 18540 KB Output is correct
21 Correct 302 ms 29168 KB Output is correct
22 Correct 151 ms 17644 KB Output is correct
23 Correct 199 ms 25016 KB Output is correct
24 Correct 191 ms 27552 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Correct 5 ms 704 KB Output is correct
15 Correct 5 ms 668 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Runtime error 6 ms 952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -