oj.uz

Submission #1049921

# Submission time Handle Problem Language Result Execution time Memory
1049921 2024-08-09T06:09:11 Z 아침연습다풀고 hamburg 풀면 복붙날먹치팅할거임(#11102) Hamburg Steak (JOI20_hamburg) C++17
0 / 100
 1 ms 348 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) {
		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.sx <= xmin && xmax <= v.ex) {
			if (v.sy <= ymin && ymin <= v.ey)
				continue;
			if (v.sy <= ymax && ymax <= v.ey)
				continue;
			// two cross |
			w.push_back(v);
		}
		if (v.sy <= ymin && ymax <= v.ey) {
			if (v.sx <= xmin && xmin <= v.ex)
				continue;
			if (v.sx <= xmax && xmax <= v.ex)
				continue;
			// two cross -
			w.push_back(v);
		}
		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
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Integer parameter [name=x_1] equals to 0, violates the range [1, 10^9]
2 Halted 0 ms 0 KB -