oj.uz

Submission #241832

# Submission time Handle Problem Language Result Execution time Memory
241832 2020-06-25T18:42:34 Z kostia244 Hamburg Steak (JOI20_hamburg) C++17
9 / 100
 676 ms 18708 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>>(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

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.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 #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 452 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 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 4 ms 512 KB Output is correct
3 Correct 4 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 416 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 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 4 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 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 488 KB Output is correct
8 Incorrect 17 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 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 362 ms 12764 KB Output is correct
6 Correct 368 ms 12760 KB Output is correct
7 Correct 344 ms 12764 KB Output is correct
8 Correct 380 ms 12760 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 452 KB Output is correct
2 Correct 4 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 344 ms 14648 KB Output is correct
6 Correct 347 ms 14812 KB Output is correct
7 Correct 334 ms 14556 KB Output is correct
8 Correct 358 ms 15324 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 4 ms 512 KB Output is correct
3 Correct 4 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 416 KB Output is correct
7 Correct 3 ms 544 KB Output is correct
8 Correct 6 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 437 ms 12784 KB Output is correct
14 Correct 354 ms 12768 KB Output is correct
15 Correct 360 ms 12772 KB Output is correct
16 Correct 352 ms 12768 KB Output is correct
17 Correct 381 ms 12764 KB Output is correct
18 Correct 442 ms 12776 KB Output is correct
19 Correct 344 ms 15200 KB Output is correct
20 Correct 676 ms 18232 KB Output is correct
21 Correct 359 ms 15924 KB Output is correct
22 Correct 410 ms 18032 KB Output is correct
23 Correct 516 ms 17796 KB Output is correct
24 Incorrect 627 ms 18708 KB Output isn't correct

Subtask #8
0 / 79.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 4 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 488 KB Output is correct
8 Incorrect 17 ms 512 KB Output isn't correct
9 Halted 0 ms 0 KB -