oj.uz

Submission #1049726

# Submission time Handle Problem Language Result Execution time Memory
1049726 2024-08-09T04:28:54 Z 아침연습다풀고 hamburg 풀면 복붙날먹치팅할거임(#11102) Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 152 ms 37968 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);
const int MAXN = 1000005;

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);
	for (auto &v : a) {
		cin >> v.sx >> v.sy >> v.ex >> v.ey;
	}
	backtrack(a, k, k);
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 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 604 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 604 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 568 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 600 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 604 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 568 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Incorrect 3 ms 840 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 600 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 604 KB Output is correct
5 Correct 49 ms 17524 KB Output is correct
6 Correct 46 ms 17492 KB Output is correct
7 Correct 48 ms 17492 KB Output is correct
8 Correct 46 ms 17388 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 604 KB Output is correct
5 Correct 61 ms 20936 KB Output is correct
6 Correct 68 ms 24016 KB Output is correct
7 Correct 49 ms 20424 KB Output is correct
8 Correct 62 ms 31944 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 568 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 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 51 ms 22512 KB Output is correct
14 Correct 54 ms 22220 KB Output is correct
15 Correct 51 ms 23140 KB Output is correct
16 Correct 49 ms 20444 KB Output is correct
17 Correct 50 ms 21608 KB Output is correct
18 Correct 48 ms 19696 KB Output is correct
19 Correct 51 ms 24160 KB Output is correct
20 Correct 152 ms 37692 KB Output is correct
21 Correct 68 ms 25080 KB Output is correct
22 Correct 98 ms 37968 KB Output is correct
23 Correct 105 ms 36168 KB Output is correct
24 Correct 106 ms 37360 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 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 568 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 828 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 3 ms 844 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Incorrect 3 ms 840 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -