Submission #484444

#	Time	Username	Problem	Language	Result	Execution time	Memory
484444		valerikk	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	179 ms	15252 KiB

hamburg

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int INF = 1'000'000'000;

struct Point {
	int x, y;
};

ostream &operator<<(ostream &stream, const Point &p) {
	stream << p.x << " " << p.y;
	return stream;
}

struct Segment {
	int l, r;

	Segment() {}

	Segment(int l, int r) : l(l), r(r) {}
};

const Segment SEG_ALL = {1, INF};

void self_intersect(Segment &a, const Segment &b) {
	a.l = max(a.l, b.l);
	a.r = min(a.r, b.r);
}

Segment intersect(Segment a, const Segment &b) {
	self_intersect(a, b);
	return a;
}

bool inside(int x, const Segment &s) {
	return x >= s.l && x <= s.r;
}

struct Rectangle {
	Segment x, y;

	Rectangle() {}

	Rectangle(const Segment &x, const Segment &y) : x(x), y(y) {}
};

const Rectangle RECT_ALL = {SEG_ALL, SEG_ALL};

istream &operator>>(istream &stream, Rectangle &r) {
	stream >> r.x.l >> r.y.l >> r.x.r >> r.y.r;
	return stream;
}

void self_intersect(Rectangle &a, const Rectangle &b) {
	self_intersect(a.x, b.x);
	self_intersect(a.y, b.y);
}

Rectangle intersect(Rectangle a, const Rectangle &b) {
	self_intersect(a, b);
	return a;
}

bool inside(const Point &p, const Rectangle &r) {
	return inside(p.x, r.x) && inside(p.y, r.y);
}

int k;

void solve(const vector<Rectangle> &rectangles, const vector<Point> &points) {
	if ((int)points.size() == k) {
		if (rectangles.empty()) {
			for (int i = 0; i < k; ++i) {
				cout << points[i] << "\n";
			}
			exit(0);
		}

		return;
	}

	Rectangle intersection = RECT_ALL;
	for (const auto &rect : rectangles) {
		self_intersect(intersection, rect);
	}

	for (int x : {intersection.x.l, intersection.x.r}) {
		for (int y : {intersection.y.l, intersection.y.r}) {
			Point p = {x, y};
			
			auto new_points = points;
			new_points.push_back(p);
			
			vector<Rectangle> new_rectangles;
			for (const auto &rect : rectangles) {
				if (!inside(p, rect)) {
					new_rectangles.push_back(rect);
				}
			}

			solve(new_rectangles, new_points);
		}
	}

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n >> k;
	vector<Rectangle> rectangles(n);
	for (auto &rect : rectangles) {
		cin >> rect;
	}

	solve(rectangles, vector<Point>{});
	
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79