oj.uz

Submission #241829

# Submission time Handle Problem Language Result Execution time Memory
241829 2020-06-25T16:48:57 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
9 / 100
 498 ms 18680 KB 
#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>>(k, {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;
	}
	if(k == 4) {
		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;
		}
	}
	if(k == 4) {
		int p = 0;
		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

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:58: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]
   58 |   if(!t.empty() && t.size() < k) {
      |                    ~~~~~~~~~^~~
hamburg.cpp:70: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]
   70 |   if(!t.empty() && t.size() < k) {
      |                    ~~~~~~~~~^~~
hamburg.cpp:78: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]
   78 |   if(!t.empty() && t.size() < k) {
      |                    ~~~~~~~~~^~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:102: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]
  102 |  while(ans.size() < k) ans.push_back({1, 1});
      |        ~~~~~~~~~~~^~~

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Incorrect 8 ms 512 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 383 ms 12764 KB Output is correct
6 Correct 345 ms 12764 KB Output is correct
7 Correct 358 ms 12832 KB Output is correct
8 Correct 441 ms 12820 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 354 ms 14820 KB Output is correct
6 Correct 347 ms 14808 KB Output is correct
7 Correct 341 ms 14600 KB Output is correct
8 Correct 353 ms 15336 KB Output is correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 544 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 379 ms 12796 KB Output is correct
14 Correct 378 ms 12776 KB Output is correct
15 Correct 377 ms 12800 KB Output is correct
16 Correct 390 ms 12784 KB Output is correct
17 Correct 362 ms 12892 KB Output is correct
18 Correct 352 ms 12764 KB Output is correct
19 Correct 355 ms 15172 KB Output is correct
20 Correct 471 ms 18268 KB Output is correct
21 Correct 359 ms 15804 KB Output is correct
22 Correct 414 ms 18156 KB Output is correct
23 Correct 375 ms 18024 KB Output is correct
24 Incorrect 498 ms 18680 KB Output isn't correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Incorrect 8 ms 512 KB Output isn't correct
9 Halted 0 ms 0 KB -