Submission #787786

#	Time	Username	Problem	Language	Result	Execution time	Memory
787786		onjo0127	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	1104 ms	157364 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vpi = vector<pii>;
using vvi = vector<vi>;
const vector<pii> EMP = {};
 
int f(vi &X, int x) { return lower_bound(X.begin(), X.end(), x) - X.begin() + 1; }
pii its(pii l, pii r) { return {max(l.first, r.first), min(l.second, r.second)}; }

vi X, Y; int XS, YS;
 
vvi rem(vvi &A, int x, int y) {
	vvi ret;
	for(auto& it: A) if(it[2] < x || x < it[0] || it[3] < y || y < it[1]) ret.push_back(it);
	return ret;
}
 
vvi intersect_line(vvi &A, int x, int y) {
	vvi ret;
	if(x) for(auto& it: A) if(it[0] <= x || x <= it[2]) ret.push_back(it);
	if(y) for(auto& it: A) if(it[1] <= y || y <= it[3]) ret.push_back(it);
	return ret;
}
 
vpi sol4(vvi A) {
	int mnr = XS, mxl = 1, mnu = YS, mxd = 1;
	for(auto& it: A) {
		mnr = min(mnr, it[2]);
		mxl = max(mxl, it[0]);
		mnu = min(mnu, it[3]);
		mxd = max(mxd, it[1]);
	}
	vvi B;
	for(auto& it: A) {
		int cnt = 0;
		for(auto& x: {mnr, mxl}) for(auto& y: {mnu, mxd}) if(it[0] <= x && x <= it[2] && it[1] <= y && y <= it[3]) ++cnt;
		if(cnt <= 1) B.push_back(it);
	}
	A = B;
	for(auto& it: A) if(mnr < it[0] && it[2] < mxl && mnu < it[1] && it[3] < mxd) return EMP;
 
	vvi L = intersect_line(A, mnr, 0);
	int only_L_mxd = mnu + 1, only_L_mnu = mxd - 1;
	for(auto& it: L) if(it[2] < mxl && mnu < it[1] && it[3] < mxd) {
		only_L_mxd = max(only_L_mxd, it[1]);
		only_L_mnu = min(only_L_mnu, it[3]);
	}
 
	vi D_mnr(YS + 1, mxl - 1);
	for(auto& it: L) D_mnr[it[3]] = min(D_mnr[it[3]], it[2]);
	for(int i=1; i<=YS; i++) D_mnr[i] = min(D_mnr[i-1], D_mnr[i]);
 
	vi U_mnr(YS + 2, mxl - 1);
	for(auto& it: L) U_mnr[it[1]] = min(U_mnr[it[1]], it[2]);
	for(int i=YS; i>=1; i--) U_mnr[i] = min(U_mnr[i+1], U_mnr[i]);
 
 	vvi U = intersect_line(A, 0, mxd);
	int new_mnr = mxl - 1;
	for(auto& it: U) if(mnr < it[0] && it[2] < mxl) new_mnr = min(new_mnr, it[2]);
 
	int only_D_mnr = mxl - 1;
	vvi D = intersect_line(A, 0, mnu);
	for(auto& it: D) if(mnr < it[0] && it[2] < mxl && it[3] < mxd) only_D_mnr = min(only_D_mnr, it[2]);

	vvi UD = intersect_line(D, 0, mxd);
	vi UD_mnr(XS + 2, mxl - 1);
	for(auto& it: UD) UD_mnr[it[0]] = min(UD_mnr[it[0]], it[2]);
	for(int i=XS; i>=1; i--) UD_mnr[i] = min(UD_mnr[i+1], UD_mnr[i]);
 
	vvi R = intersect_line(A, mxl, 0);
	vvi RU = intersect_line(R, 0, mxd);
	vvi RD = intersect_line(R, 0, mnu);
 
	vi RU_mxd(XS + 2, mnu + 1);
	for(auto& it: RU) if(it[1] > mnu) RU_mxd[it[0]] = max(RU_mxd[it[0]], it[1]);
	for(int i=XS; i>=1; i--) RU_mxd[i] = max(RU_mxd[i+1], RU_mxd[i]);
 
	vi RD_mnu(XS + 2, mxd - 1);
	for(auto& it: RD) if(it[3] < mxd) RD_mnu[it[0]] = min(RD_mnu[it[0]], it[3]);
	for(int i=XS; i>=1; i--) RD_mnu[i] = min(RD_mnu[i+1], RD_mnu[i]);
 
	int only_R_mxd = mnu + 1, only_R_mnu = mxd - 1;
	for(auto& it: R) if(it[1] > mnu && it[3] < mxd && mnr < it[0]) {
		only_R_mxd = max(only_R_mxd, it[1]);
		only_R_mnu = min(only_R_mnu, it[3]);
	}

	vvi LR = intersect_line(R, mnr, 0);
	vpi LRU(YS + 1, {mnu + 1, mxd - 1}), LRD(YS + 2, {mnu + 1, mxd - 1});
	for(auto& it: LR) if(it[1] > mnu && it[3] < mxd) {
		LRU[it[3]] = its(LRU[it[3]], {it[1], it[3]});
		LRD[it[1]] = its(LRD[it[1]], {it[1], it[3]});
	}
	for(int i=1; i<=YS; i++) LRU[i] = its(LRU[i-1], LRU[i]);
	for(int i=YS; i>=1; i--) LRD[i] = its(LRD[i+1], LRD[i]);
 
	for(int ly=only_L_mxd; ly<=only_L_mnu; ly++) {
		int ux = min(U_mnr[ly + 1], new_mnr);
		int dx = min({D_mnr[ly - 1], only_D_mnr, UD_mnr[ux + 1]});
		int r_mxd = max({RU_mxd[ux + 1], only_R_mxd, LRU[ly - 1].first, LRD[ly + 1].first});
		int r_mnu = min({RD_mnu[dx + 1], only_R_mnu, LRU[ly - 1].second, LRD[ly + 1].second});
		//printf("ly: %d, ux: %d, dx: %d, r_mxd: %d, r_mnu: %d\n", ly, ux, dx, r_mxd, r_mnu);
		if(ux <= dx && r_mxd <= r_mnu) return {{mnr, ly}, {ux, mxd}, {dx, mnu}, {mxl, r_mxd}};
	}
 
	return EMP;
}
 
vpi sol(vvi &A, int K) {
	int mnr = XS, mxl = 1, mnu = YS, mxd = 1;
	for(auto& it: A) {
		mnr = min(mnr, it[2]);
		mxl = max(mxl, it[0]);
		mnu = min(mnu, it[3]);
		mxd = max(mxd, it[1]);
	}
	if(K == 1) {	
		if(mxl <= mnr && mxd <= mnu) return {{mxl, mxd}};
		return EMP;
	}
	if(K == 2) {
		vvi B; vpi S;
		for(auto y: {mxd, mnu}) {
			B = rem(A, mxl, y);
			S = sol(B, 1);
			if(S.size()) return {{mxl, y}, S[0]};
		}
		return EMP;
	}
	if(K == 3) {
		vvi B; vpi S;
		for(auto x: {mxl, mnr}) for(auto y: {mxd, mnu}) {
			B = rem(A, x, y);
			S = sol(B, 2);
			if(S.size()) return {{x, y}, S[0], S[1]};
		}
		return EMP;
	}
	if(K == 4) {
		vvi B; vpi S;
		for(auto x: {mxl, mnr}) for(auto y: {mxd, mnu}) {
			B = rem(A, x, y);
			S = sol(B, 3);
			if(S.size()) return {{x, y}, S[0], S[1], S[2]};
		}
		S = sol4(A);
		if(S.size()) return S;
		for(auto& it: A) it = {XS - it[2] + 1, it[1], XS - it[0] + 1, it[3]};
		S = sol4(A);
		for(auto& it: A) it = {XS - it[2] + 1, it[1], XS - it[0] + 1, it[3]};
		if(S.size()) {
			for(auto& [x, y]: S) x = XS - x + 1;
			return S;
		}
		return EMP;
	}
}

int rnd(int l, int r) {
	return l + rand() % (r-l+1);
}

int main() {
	vvi A; 
	int N, K; scanf("%d%d", &N, &K);
	for(int i=0; i<N; i++) {
		vi H(4);
		for(int j=0; j<4; j++) scanf("%d", &H[j]);
		A.push_back(H);
		X.push_back(H[0]);
		X.push_back(H[2]);
		Y.push_back(H[1]);
		Y.push_back(H[3]);
	}
	sort(X.begin(), X.end()); X.resize(unique(X.begin(), X.end()) - X.begin()); XS = X.size();
	sort(Y.begin(), Y.end()); Y.resize(unique(Y.begin(), Y.end()) - Y.begin()); YS = Y.size();
	for(auto& it: A) {
		it[0] = f(X, it[0]);
		it[1] = f(Y, it[1]);
		it[2] = f(X, it[2]);
		it[3] = f(Y, it[3]);
	}
	vpi ans;
	for(int k=1; k<=K && ans.empty(); k++) ans = sol(A, k);
	assert(!ans.empty());
	while((int)ans.size() < K) ans.push_back({1, 1});
	for(auto& [x, y]: ans) printf("%d %d\n", X[x-1], Y[y-1]);
	/*
	int N = 5, K = 4;
	srand(1235);
	while(1) {
		vvi A;
		X.clear();
		Y.clear();
		for(int i=0; i<N; i++) {
			vi H = {rnd(1, 2*N), rnd(1, 2*N), rnd(1, 2*N), rnd(1, 2*N)};
			if(H[0] > H[2]) swap(H[0], H[2]);
			if(H[1] > H[3]) swap(H[1], H[3]);
			A.push_back(H);
			X.push_back(H[0]);
			X.push_back(H[2]);
			Y.push_back(H[1]);
			Y.push_back(H[3]);
		}
		sort(X.begin(), X.end()); X.resize(unique(X.begin(), X.end()) - X.begin()); XS = X.size();
		sort(Y.begin(), Y.end()); Y.resize(unique(Y.begin(), Y.end()) - Y.begin()); YS = Y.size();
		for(auto& it: A) {
			it[0] = f(X, it[0]);
			it[1] = f(Y, it[1]);
			it[2] = f(X, it[2]);
			it[3] = f(Y, it[3]);
		}
		vpi ans;
		for(int k=1; k<=K && ans.empty(); k++) ans = sol(A, k);
		if(ans.empty()) {
			for(auto& it: A) printf("%d %d %d %d\n", it[0], it[1], it[2], it[3]);
			return 0;
		}
	}
	*/
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'vpi sol(vvi&, int)':
hamburg.cpp:159:1: warning: control reaches end of non-void function [-Wreturn-type]
  159 | }
      | ^
hamburg.cpp: In function 'int main()':
hamburg.cpp:167:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |  int N, K; scanf("%d%d", &N, &K);
      |            ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:170:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |   for(int j=0; j<4; j++) scanf("%d", &H[j]);
      |                          ~~~~~^~~~~~~~~~~~~

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