Submission #484433

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
484433	2021-11-03T10:49:51 Z	valerikk	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	334 ms	35376 KB

hamburg

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e9;

struct Rect {
	int l, d, r, u;

	bool operator()(int x, int y) {
		return l <= x && x <= r && d <= y && y <= u;
	}
};

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

void out(int k, vector<pair<int, int>> points) {
	for (int i = 0; i < k; ++i) {
		auto [x, y] = points[min(i, (int)points.size() -  1)];
		cout << x << " " << y << "\n";
	}
	exit(0);
}

void rec(vector<Rect> rects, int k, vector<pair<int, int>> points) {
	for (auto [x, y] : points) {
		rects = filter(rects, x, y);
	}

	if (rects.empty()) {
		out(k, points);
	}

	if ((int)points.size() == k) {
		return;
	}

	int maxl = 1, minr = INF, maxd = 1, minu = INF;
	for (auto r : rects) {
		maxl = max(maxl, r.l);
		minr = min(minr, r.r);
		maxd = max(maxd, r.d);
		minu = min(minu, r.u);
	}

	if (maxd <= minu) {
		sort(rects.begin(), rects.end(), [&](Rect r1, Rect r2) {
			return r1.r < r2.r;
		});
		for (auto r : rects) {
			bool ok = false;
			for (auto [x, y] : points) {
				ok |= r(x, y); 
			}
			if (!ok) {
				if ((int)points.size() == k) {
					return;
				}
				points.push_back({r.r, maxd});
			}
		}
		out(k, points);
	}

	if (maxl <= minr) {
		sort(rects.begin(), rects.end(), [&](Rect r1, Rect r2) {
			return r1.u < r2.u;
		});
		for (auto r : rects) {
			bool ok = false;
			for (auto [x, y] : points) {
				ok |= r(x, y);
			}
			if (!ok) {
				if ((int)points.size() == k) {
					return;
				}
				points.push_back({maxl, r.u});
			}
		}
		out(k, points);
	}

	for (int x : {maxl, minr}) {
		for (int y : {maxd, minu}) {
			points.push_back({x, y});
			rec(rects, k, points);
			points.pop_back();
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	vector<Rect> rects(n);
	for (auto &r : rects) {
		cin >> r.l >> r.d >> r.r >> r.u;
	}
	vector<pair<int, int>> points;
	rec(rects, k, points);
	return 0;
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	456 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	420 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	3 ms	588 KB	Output is correct
9	Correct	1 ms	588 KB	Output is correct
10	Correct	2 ms	580 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct

Subtask #4
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	588 KB	Output is correct
8	Correct	8 ms	692 KB	Output is correct
9	Correct	3 ms	580 KB	Output is correct
10	Correct	7 ms	668 KB	Output is correct
11	Correct	9 ms	692 KB	Output is correct
12	Correct	3 ms	588 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Incorrect	7 ms	672 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	1 ms	332 KB	Output is correct
2	Correct	1 ms	448 KB	Output is correct
3	Correct	1 ms	424 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	96 ms	14308 KB	Output is correct
6	Correct	90 ms	14312 KB	Output is correct
7	Correct	88 ms	14276 KB	Output is correct
8	Correct	95 ms	14212 KB	Output is correct

Subtask #6
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	2 ms	460 KB	Output is correct
3	Correct	2 ms	460 KB	Output is correct
4	Correct	2 ms	580 KB	Output is correct
5	Correct	85 ms	22640 KB	Output is correct
6	Correct	95 ms	25172 KB	Output is correct
7	Correct	83 ms	22720 KB	Output is correct
8	Correct	110 ms	29896 KB	Output is correct

Subtask #7
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	456 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	420 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	3 ms	588 KB	Output is correct
9	Correct	1 ms	588 KB	Output is correct
10	Correct	2 ms	580 KB	Output is correct
11	Correct	2 ms	588 KB	Output is correct
12	Correct	2 ms	460 KB	Output is correct
13	Correct	88 ms	14308 KB	Output is correct
14	Correct	90 ms	14320 KB	Output is correct
15	Correct	88 ms	14424 KB	Output is correct
16	Correct	87 ms	14188 KB	Output is correct
17	Correct	94 ms	14276 KB	Output is correct
18	Correct	88 ms	14280 KB	Output is correct
19	Correct	86 ms	26696 KB	Output is correct
20	Correct	334 ms	35376 KB	Output is correct
21	Correct	94 ms	26812 KB	Output is correct
22	Correct	178 ms	33788 KB	Output is correct
23	Correct	224 ms	33296 KB	Output is correct
24	Correct	187 ms	32752 KB	Output is correct

Subtask #8
0 / 79.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	460 KB	Output is correct
2	Correct	1 ms	332 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	460 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	588 KB	Output is correct
8	Correct	8 ms	692 KB	Output is correct
9	Correct	3 ms	580 KB	Output is correct
10	Correct	7 ms	668 KB	Output is correct
11	Correct	9 ms	692 KB	Output is correct
12	Correct	3 ms	588 KB	Output is correct
13	Correct	2 ms	540 KB	Output is correct
14	Incorrect	7 ms	672 KB	Unexpected end of file - int32 expected
15	Halted	0 ms	0 KB	-

Submission #484433

Compilation message