Submission #787466

#	Time	Username	Problem	Language	Result	Execution time	Memory
787466		onjo0127	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	360 ms	41124 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; }

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]);
	}
	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);

	sort(L.begin(), L.end(), [&](vi p, vi q) { return p[3] < q[3]; });
	vi D_mnr(YS + 1, XS + 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]);

	sort(L.begin(), L.end(), [&](vi p, vi q) { return p[1] > q[1]; });
	vi U_mnr(YS + 2, XS + 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]);

	int new_mnr = XS + 1;
	for(auto& it: A) if(mnr < it[0]) new_mnr = min(new_mnr, it[2]);

	int only_D_mnr = XS + 1;
	vvi D = intersect_line(A, 0, mnu);
	for(auto& it: D) if(mnr < it[0] && it[3] < mxd) only_D_mnr = min(only_D_mnr, it[2]);

	vvi UD = intersect_line(D, 0, mxd);
	sort(UD.begin(), UD.end(), [&](vi p, vi q) { return p[0] > q[0]; });
	vi UD_mnr(XS + 2, XS + 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); sort(R.begin(), R.end(), [&](vi p, vi q) { return p[0] > q[0]; });
	vvi RU = intersect_line(R, 0, mxd); sort(RU.begin(), RU.end(), [&](vi p, vi q) { return p[0] > q[0]; });
	vvi RD = intersect_line(R, 0, mnu); sort(RD.begin(), RD.end(), [&](vi p, vi q) { return p[0] > q[0]; });

	vi RU_mxd(XS + 2, 0);
	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, YS + 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 = 0, only_R_mnu = YS + 1;
	for(auto& it: R) if(it[1] > mnu && it[3] < mxd) {
		only_R_mxd = max(only_R_mxd, it[1]);
		only_R_mnu = min(only_R_mnu, it[3]);
	}

	for(int ly=2; ly<YS; 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);
		int r_mnu = min(RD_mnu[dx + 1], only_R_mnu);
		if(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);
		if(S.size()) {
			for(auto& [x, y]: S) x = XS - x + 1;
			return S;
		}
		return EMP;
	}
}

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]);
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'vpi sol(vvi&, int)':
hamburg.cpp:137:1: warning: control reaches end of non-void function [-Wreturn-type]
  137 | }
      | ^
hamburg.cpp: In function 'int main()':
hamburg.cpp:141:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  int N, K; scanf("%d%d", &N, &K);
      |            ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:144:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |   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: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79