oj.uz

Submission #787443

# Submission time Handle Problem Language Result Execution time Memory
787443 2023-07-19T07:57:27 Z onjo0127 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 346 ms 40908 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, int mxl, int mnu, int mxd) {
	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, mnr, mxl, mnu, mxd);
		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, mnr, mxl, mnu, mxd);
		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:132:1: warning: control reaches end of non-void function [-Wreturn-type]
  132 | }
      | ^
hamburg.cpp: In function 'int main()':
hamburg.cpp:136:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |  int N, K; scanf("%d%d", &N, &K);
      |            ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:139:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |   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 3 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 3 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 564 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 3 ms 564 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 4 ms 824 KB Output is correct
11 Correct 5 ms 868 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 2 ms 568 KB Output is correct
14 Runtime error 10 ms 1488 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 3 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 14292 KB Output is correct
6 Correct 283 ms 14404 KB Output is correct
7 Correct 267 ms 14404 KB Output is correct
8 Correct 272 ms 14400 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 277 ms 20284 KB Output is correct
6 Correct 272 ms 23644 KB Output is correct
7 Correct 265 ms 20028 KB Output is correct
8 Correct 280 ms 28868 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 3 ms 724 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 3 ms 564 KB Output is correct
13 Correct 279 ms 23492 KB Output is correct
14 Correct 273 ms 23084 KB Output is correct
15 Correct 275 ms 24620 KB Output is correct
16 Correct 274 ms 20672 KB Output is correct
17 Correct 282 ms 22208 KB Output is correct
18 Correct 264 ms 18856 KB Output is correct
19 Correct 281 ms 25216 KB Output is correct
20 Correct 346 ms 40908 KB Output is correct
21 Correct 276 ms 28496 KB Output is correct
22 Correct 299 ms 39732 KB Output is correct
23 Correct 333 ms 38596 KB Output is correct
24 Correct 314 ms 35768 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 3 ms 564 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 568 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 5 ms 852 KB Output is correct
9 Correct 3 ms 700 KB Output is correct
10 Correct 4 ms 824 KB Output is correct
11 Correct 5 ms 868 KB Output is correct
12 Correct 3 ms 724 KB Output is correct
13 Correct 2 ms 568 KB Output is correct
14 Runtime error 10 ms 1488 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -