Submission #1213181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213181		siewjh	Hamburg Steak (JOI20_hamburg)	C++20	15 / 100	64 ms	6580 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int inf = 1e9 + 7;
int la[MAXN], ra[MAXN], da[MAXN], ua[MAXN];
vector<pair<int, int>> ans;
bool in(int id, int x, int y){
	return x >= la[id] && x <= ra[id] && y >= da[id] && y <= ua[id];
}
bool solve(vector<int> &vid, int scnt){
	if (scnt == 0) return vid.empty();
	int l = -1, r = inf, d = -1, u = inf;
	for (int x : vid){
		l = max(l, la[x]); r = min(r, ra[x]); d = max(d, da[x]); u = min(u, ua[x]);
	}
	if (l <= r){
		if (d <= u){
			ans.push_back({l, d}); return 1;
		}
		else{
			if (scnt < 2) return 0;
			vector<int> nvid;
			for (int x : vid)
				if (!in(x, l, d) && !in(x, l, u))
					nvid.push_back(x);
			if (solve(nvid, scnt - 2)){
				ans.push_back({l, d}); ans.push_back({l, u});
				return 1;
			}
			else return 0;
		}
	}
	else{
		if (d <= u){
			if (scnt < 2) return 0;
			vector<int> nvid;
			for (int x : vid)
				if (!in(x, l, u) && !in(x, r, u))
					nvid.push_back(x);
			if (solve(nvid, scnt - 2)){
				ans.push_back({l, u}); ans.push_back({r, u});
				return 1;
			}
			else return 0;
		}
		else{
			if (scnt < 2) return 0;
			pair<int, int> corn[4] = {{l, u}, {l, d}, {r, u}, {r, d}};
			for (auto [cx, cy] : corn){
				vector<int> nvid;
				for (int x : vid)
					if (!in(x, cx, cy))
						nvid.push_back(x);
				if (solve(nvid, scnt - 1)){
					ans.push_back({cx, cy});
					return 1;
				}
			}
			return 0;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nums, snum; cin >> nums >> snum;
	for (int i = 0; i < nums; i++) cin >> la[i] >> da[i] >> ra[i] >> ua[i];
	vector<int> vid;
	for (int i = 0; i < nums; i++) vid.push_back(i);
	solve(vid, snum);
	for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
	for (int sz = ans.size(); sz < snum; sz++) cout << 1 << ' ' << 1 << '\n';
}

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