oj.uz

Submission #787705

# Submission time Handle Problem Language Result Execution time Memory
787705 2023-07-19T11:20:32 Z onjo0127 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 364 ms 42544 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; }
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[3]);
		only_L_mnu = min(only_L_mnu, it[1]);
	}
 
	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_mnu; ly<=only_L_mxd; 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

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

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 696 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 724 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 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 692 KB Output is correct
8 Correct 5 ms 900 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 784 KB Output is correct
11 Correct 5 ms 824 KB Output is correct
12 Correct 3 ms 716 KB Output is correct
13 Correct 3 ms 708 KB Output is correct
14 Correct 6 ms 1200 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Incorrect 6 ms 1320 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 2 ms 436 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 262 ms 18248 KB Output is correct
6 Correct 259 ms 18028 KB Output is correct
7 Correct 262 ms 18156 KB Output is correct
8 Correct 259 ms 18028 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 516 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 540 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 267 ms 23116 KB Output is correct
6 Correct 275 ms 26308 KB Output is correct
7 Correct 267 ms 22636 KB Output is correct
8 Correct 283 ms 31552 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 696 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 724 KB Output is correct
12 Correct 3 ms 564 KB Output is correct
13 Correct 337 ms 28300 KB Output is correct
14 Correct 286 ms 28596 KB Output is correct
15 Correct 294 ms 30112 KB Output is correct
16 Correct 275 ms 23836 KB Output is correct
17 Correct 287 ms 29760 KB Output is correct
18 Correct 277 ms 22988 KB Output is correct
19 Correct 287 ms 34988 KB Output is correct
20 Correct 364 ms 42160 KB Output is correct
21 Correct 300 ms 35772 KB Output is correct
22 Correct 314 ms 42544 KB Output is correct
23 Correct 339 ms 40744 KB Output is correct
24 Correct 313 ms 39084 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 696 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 4 ms 692 KB Output is correct
8 Correct 5 ms 900 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 4 ms 784 KB Output is correct
11 Correct 5 ms 824 KB Output is correct
12 Correct 3 ms 716 KB Output is correct
13 Correct 3 ms 708 KB Output is correct
14 Correct 6 ms 1200 KB Output is correct
15 Correct 3 ms 724 KB Output is correct
16 Correct 3 ms 724 KB Output is correct
17 Incorrect 6 ms 1320 KB Output isn't correct
18 Halted 0 ms 0 KB -