oj.uz

Submission #1049928

# Submission time Handle Problem Language Result Execution time Memory
1049928 2024-08-09T06:10:42 Z 아침연습다풀고 hamburg 풀면 복붙날먹치팅할거임(#11102) Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 151 ms 29436 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);

struct rect {
	int sx, sy, ex, ey;
};

vector<pi> trace;

vector<rect> chop(vector<rect> a, pi p) {
	vector<rect> z;
	for (auto &r : a) {
		if (r.sx <= p[0] && p[0] <= r.ex && r.sy <= p[1] && p[1] <= r.ey)
			continue;
		z.push_back(r);
	}
	return z;
}

void backtrack(vector<rect> a, int k, int p) {
	if (sz(a) == 0) {
		for (int i = 0; i < p; i++) {
			cout << trace[i % sz(trace)][0] << " " << trace[i % sz(trace)][1] << "\n";
		}
		exit(0);
	}
	if (k == 0)
		return;
	int xmin = 2e9, ymin = 2e9, xmax = -2e9, ymax = -2e9;
	for (auto &x : a) {
		xmin = min(xmin, x.ex);
		ymin = min(ymin, x.ey);
		xmax = max(xmax, x.sx);
		ymax = max(ymax, x.sy);
	}
	vector<pi> cp = {pi{xmax, ymax}, pi{xmax, ymin}, pi{xmin, ymax}, pi{xmin, ymin}};
	for (auto &v : cp) {
		trace.push_back(v);
		backtrack(chop(a, v), k - 1, p);
		trace.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<rect> a(n);
	int xmin = 2e9, ymin = 2e9, xmax = -2e9, ymax = -2e9;
	for (auto &x : a) {
		cin >> x.sx >> x.sy >> x.ex >> x.ey;
		xmin = min(xmin, x.ex);
		ymin = min(ymin, x.ey);
		xmax = max(xmax, x.sx);
		ymax = max(ymax, x.sy);
	}
	backtrack(a, k, k);
	assert(xmin < xmax && ymin < ymax);
	vector<rect> w;
	int is = ymin + 1, ie = ymax - 1;
	for (auto &v : a) {
		if (v.ex < xmax && v.sy > ymin && v.ey < ymax) {
			is = max(is, v.sy);
			ie = min(ie, v.ey);
		}
	}
	a = w;
	for (auto &v : a) {
		if (v.ey >= is && v.ey <= ie) {
			trace.push_back({xmin, v.ey});
			backtrack(chop(a, trace[0]), k - 1, k);
			trace.pop_back();
		}
	}
}

Subtask #1
1.0 / 1.0

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

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 804 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Incorrect 2 ms 604 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 46 ms 9716 KB Output is correct
6 Correct 45 ms 9732 KB Output is correct
7 Correct 46 ms 9728 KB Output is correct
8 Correct 46 ms 9820 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 47 ms 13004 KB Output is correct
6 Correct 54 ms 16256 KB Output is correct
7 Correct 48 ms 12676 KB Output is correct
8 Correct 60 ms 24172 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 484 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 740 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 48 ms 14796 KB Output is correct
14 Correct 48 ms 14536 KB Output is correct
15 Correct 48 ms 15304 KB Output is correct
16 Correct 54 ms 12744 KB Output is correct
17 Correct 54 ms 13936 KB Output is correct
18 Correct 46 ms 11980 KB Output is correct
19 Correct 48 ms 15812 KB Output is correct
20 Correct 151 ms 29148 KB Output is correct
21 Correct 53 ms 18632 KB Output is correct
22 Correct 80 ms 29436 KB Output is correct
23 Correct 109 ms 28416 KB Output is correct
24 Correct 90 ms 27936 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 804 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 5 ms 604 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Incorrect 2 ms 604 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -