Submission #241832

#	Time	Username	Problem	Language	Result	Execution time	Memory
241832		kostia244	Hamburg Steak (JOI20_hamburg)	C++17	9 / 100	676 ms	18708 KiB

hamburg

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int inf = 1<<30;
int n, k;
vector<int> cd[2] = {{-inf, inf}, {-inf, inf}};
vector<array<int, 4>> cut(vector<array<int, 4>> rects, array<int, 2> p) {
	for(int i = rects.size(); i--;) {
		auto r = rects[i];
		if(r[0] <= p[0] && p[0] <= r[2] && r[1] <= p[1] && p[1] <= r[3])
			swap(rects[i], rects.back()), rects.pop_back();
	}
	return rects;
}
vector<array<int, 2>> solve(vector<array<int, 4>> rects, int k) {
	if(k == 0) return {};
	if(rects.empty()) return vector<array<int, 2>>(1, {1, 1});
	array<int, 4> bounds;
	bounds[2] = bounds[3] = n + 2;
	bounds[0] = bounds[1] = 0;
	for(auto i : rects)
		for(int j = 0; j < 4; j++)
			bounds[j] = (j > 1 ? min(bounds[j], i[j]) : max(bounds[j], i[j]));
	//cout << bounds[0] << " " << bounds[1] << " " << bounds[2] << " " << bounds[3] << endl;
	if(bounds[0] <= bounds[2] || bounds[1] <= bounds[3]) {
		int rev = 0;
		if(bounds[0] > bounds[2]) {
			swap(bounds[0], bounds[1]), swap(bounds[2], bounds[3]);
			for(auto &i : rects)
				swap(i[0], i[1]), swap(i[2], i[3]), rev = 1;
		}
		vector<array<int, 2>> segs, ans;
		for(auto &i : rects) segs.push_back({i[1], i[3]});//, cout << i[0] << " " << i[1] << " " << i[2] << " " << i[3] << '\n';
		sort(all(segs), greater<>());
		int c = inf;
		for(auto i : segs) {
			//cout << i[0] << " " << i[1] << '\n';
			if(i[1] < c) {
				c = i[0];
				ans.push_back(rev ? array<int, 2>{c, bounds[0]} : array<int, 2>{bounds[0], c});
			}
		}
		if(rev) {
			swap(bounds[0], bounds[1]), swap(bounds[2], bounds[3]);
			for(auto &i : rects)
				swap(i[0], i[1]), swap(i[2], i[3]), rev = 1;
		}
		if(ans.size() <= k)
			return ans;
	}
	{int p = 0;
	for(auto i : rects) {
		 if(i[0] <= bounds[0] && bounds[0] <= i[2]) p = max(p, i[1]);
	}
	array<int, 2> P = {bounds[0], p};
	auto t = solve(cut(rects, P), k-1);
	if(!t.empty() && t.size() < k) {
		t.push_back(P);
		return t;
	}
	}
	{int p = n+2;
	for(auto i : rects) {
		 if(i[0] <= bounds[0] && bounds[0] <= i[2]) p = min(p, i[3]);
	}
	array<int, 2> P = {bounds[0], p};
	auto t = solve(cut(rects, P), k-1);
	if(!t.empty() && t.size() < k) {
		t.push_back(P);
		return t;
	}
	}	
	for(int i = 0; i < 4; i++) {
		array<int, 2> P {bounds[2*(i&1)], bounds[1 + (i&2)]};
		auto t = solve(cut(rects, P), k-1);
		if(!t.empty() && t.size() < k) {
			t.push_back(P);
			return t;
		}
	}
	return {};
	//while(true);
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	vector<array<int, 4>> rects(n);
	for(auto &i : rects)
		for(int j = 0; j < 4; j++) {
			cin >> i[j];
			cd[j&1].push_back(i[j]);
		}
	
	for(int i : {0, 1}) sort(all(cd[i]));
	for(auto &i : rects)
		for(int j = 0; j < 4; j++) {
			i[j] = lower_bound(all(cd[j&1]), i[j]) - cd[j&1].begin();
		}
	auto ans = solve(rects, k);
	while(ans.size() < k) ans.push_back({1, 1});
	for(auto [x, y] : ans) cout << cd[0][x] << " " << cd[1][y] << '\n';
	/*cout << " ------------- \n";
	for(auto [x, y] : ans) cout << x << " " << y << '\n';
	for(auto i : ans) rects = cut(rects, i);
	for(auto i : rects) cout << i[0] << " " << i[1] << " " << i[2] << " " << i[3] << '\n';
	assert(rects.empty());*/
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<std::array<int, 2> > solve(std::vector<std::array<int, 4> >, int)':
hamburg.cpp:48:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |   if(ans.size() <= k)
      |      ~~~~~~~~~~~^~~~
hamburg.cpp:57:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |  if(!t.empty() && t.size() < k) {
      |                   ~~~~~~~~~^~~
hamburg.cpp:68:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |  if(!t.empty() && t.size() < k) {
      |                   ~~~~~~~~~^~~
hamburg.cpp:76:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |   if(!t.empty() && t.size() < k) {
      |                    ~~~~~~~~~^~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:100:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |  while(ans.size() < k) ans.push_back({1, 1});
      |        ~~~~~~~~~~~^~~

• 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: 0 / 6
• Subtask 8: 0 / 79