oj.uz

Submission #241825

# Submission time Handle Problem Language Result Execution time Memory
241825 2020-06-25T15:38:53 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
9 / 100
 462 ms 18672 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});
			}
		}
		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.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.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 'int main()':
hamburg.cpp:84: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]
   84 |  while(ans.size() < k) ans.push_back({1, 1});
      |        ~~~~~~~~~~~^~~

Subtask #1
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 3 ms 512 KB Output is correct
4 Correct 3 ms 488 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 3 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 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 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 488 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 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 4 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 3 ms 512 KB Output is correct
8 Incorrect 6 ms 616 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 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 488 KB Output is correct
5 Correct 408 ms 12888 KB Output is correct
6 Correct 350 ms 12764 KB Output is correct
7 Correct 394 ms 12760 KB Output is correct
8 Correct 374 ms 12808 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 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 358 ms 14680 KB Output is correct
6 Correct 363 ms 14808 KB Output is correct
7 Correct 364 ms 14552 KB Output is correct
8 Correct 364 ms 15408 KB Output is correct

Subtask #7
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 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 488 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 357 ms 12764 KB Output is correct
14 Correct 370 ms 12760 KB Output is correct
15 Correct 366 ms 12976 KB Output is correct
16 Correct 362 ms 12888 KB Output is correct
17 Correct 352 ms 12768 KB Output is correct
18 Correct 364 ms 12760 KB Output is correct
19 Correct 340 ms 15192 KB Output is correct
20 Correct 446 ms 18264 KB Output is correct
21 Correct 346 ms 15796 KB Output is correct
22 Correct 413 ms 18244 KB Output is correct
23 Correct 400 ms 18068 KB Output is correct
24 Incorrect 462 ms 18672 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 4 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 3 ms 512 KB Output is correct
8 Incorrect 6 ms 616 KB Output isn't correct
9 Halted 0 ms 0 KB -