oj.uz

Submission #787449

# Submission time Handle Problem Language Result Execution time Memory
787449 2023-07-19T08:04:09 Z onjo0127 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 365 ms 40376 KB 
#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, mxl, 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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Runtime error 57 ms 2372 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 260 ms 14396 KB Output is correct
6 Correct 263 ms 14428 KB Output is correct
7 Correct 256 ms 14396 KB Output is correct
8 Correct 259 ms 14328 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 279 ms 20284 KB Output is correct
6 Correct 271 ms 23780 KB Output is correct
7 Correct 258 ms 20028 KB Output is correct
8 Correct 279 ms 28876 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 273 ms 22976 KB Output is correct
14 Correct 284 ms 22468 KB Output is correct
15 Correct 270 ms 24092 KB Output is correct
16 Correct 287 ms 20160 KB Output is correct
17 Correct 267 ms 21692 KB Output is correct
18 Correct 269 ms 18252 KB Output is correct
19 Correct 267 ms 24648 KB Output is correct
20 Correct 365 ms 40376 KB Output is correct
21 Correct 276 ms 27912 KB Output is correct
22 Correct 304 ms 39276 KB Output is correct
23 Correct 311 ms 38084 KB Output is correct
24 Correct 291 ms 35184 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 4 ms 820 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 4 ms 724 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 3 ms 468 KB Output is correct
14 Runtime error 57 ms 2372 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -