Submission #308280

#	Time	Username	Problem	Language	Result	Execution time	Memory
308280		cki86201	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	471 ms	13536 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

const int INF = 1e9 + 10, M = 4e5 + 5;
int N, K;
vector <int> vx, vy;
struct rect {
	int x1, y1, x2, y2;
	bool In(int x, int y) {
		return x1 <= x && x <= x2 && y1 <= y && y <= y2;
	}
} R[200020];

void trial(vector <pii> ans) {
	if(szz(ans) == 0 || szz(ans) > K) return;
	while(szz(ans) < K) ans.pb(ans[0]);
	for(int i=1;i<=N;i++) {
		int r = 0;
		for(auto &[x, y] : ans) if(R[i].In(x, y)) {
			r = 1; break;
		}
		if(r == 0) return;
	}
	for(auto [x, y] : ans) printf("%d %d\n", vx[x-1], vy[y-1]);
	exit(0);
}

int arr[4*M+5];
vector <int> solve_linear(vector <pii> R) {
	for(int i=1;i<=M;i++) arr[i] = INF;
	for(auto [x, y] : R) arr[x] = min(arr[x], y);
	for(int i=M-1;i;i--) arr[i] = min(arr[i], arr[i+1]);
	vector <int> res;
	for(int t=1;arr[t]!=INF;t=arr[t]+1) res.pb(arr[t]);
	return res;
}

void solve(vector <int> rst, int k, vector <pii> ans) {
	if(szz(rst) == 0) trial(ans);
	if(k == 0) return;
	int lx = INF, rx = -INF, ly = INF, ry = -INF;
	for(int i : rst) {
		lx = min(lx, R[i].x2);
		rx = max(rx, R[i].x1);
		ly = min(ly, R[i].y2);
		ry = max(ry, R[i].y1);
	}
	if(k == 1) {
		if(lx >= rx && ly >= ry) {
			ans.pb({rx, ry});
			trial(ans);
		}
		return;
	}
	if(lx >= rx) {
		vector <pii> V;
		for(int i : rst) V.pb({R[i].y1, R[i].y2});
		auto ys = solve_linear(V);
		for(int y : ys) ans.pb({rx, y});
		trial(ans);
		return;
	}
	if(ly >= ry) {
		vector <pii> V;
		for(int i : rst) V.pb({R[i].x1, R[i].x2});
		auto xs = solve_linear(V);
		for(int x : xs) ans.pb({x, ry});
		trial(ans);
		return;
	}
	vector <pii> vert;
	for(int x : {lx, rx}) for(int y : {ly, ry}) vert.pb({x, y});
	for(auto [x, y] : vert) {
		vector <int> nst;
		for(int i : rst) if(!R[i].In(x, y)) nst.pb(i);
		auto ans2 = ans; ans2.pb({x, y});
		solve(nst, k - 1, ans2);
	}
}

int main() {
	scanf("%d%d", &N, &K);
	if(K == 4) return 0;
	for(int i=1;i<=N;i++) {
		scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
		vx.pb(R[i].x1), vx.pb(R[i].x2);
		vy.pb(R[i].y1), vy.pb(R[i].y2);
	}
	sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
	sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
	for(int i=1;i<=N;i++) {
		auto &[x1, y1, x2, y2] = R[i];
		x1 = (int)(lower_bound(all(vx), x1) - vx.begin()) + 1;
		y1 = (int)(lower_bound(all(vy), y1) - vy.begin()) + 1;
		x2 = (int)(lower_bound(all(vx), x2) - vx.begin()) + 1;
		y2 = (int)(lower_bound(all(vy), y2) - vy.begin()) + 1;
	}
	vector <int> rst;
	for(int i=1;i<=N;i++) rst.pb(i);
	solve(rst, K, {});
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d", &N, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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