Submission #218006

#	Time	Username	Problem	Language	Result	Execution time	Memory
218006		mieszko11b	Hamburg Steak (JOI20_hamburg)	C++14	6 / 100	181 ms	7672 KiB

hamburg

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

const int inf = int(1e9);

struct rect {
	int l, r, d, u;
	
	rect() {
	}
	
	rect(int l, int r, int d, int u) {
		this->l = l;
		this->r = r;
		this->d = d;
		this->u = u;
	}
};

bool rects_intersect(rect &a, rect &b) {
	return max(a.l, b.l) <= min(a.r, b.r) && max(a.d, b.d) <= min(a.u, b.u);
}

void normalise(vector<ii> &V, int dx, int dy) {
	if(dx == 1)
		sort(V.begin(), V.end());
	else
		sort(V.begin(), V.end(), greater<ii>());
		
	vector<ii> res;
	for(auto r : V) {
		while(!res.empty() && res.back().Y * dy >= r.Y * dy)
			res.pop_back();
		if(res.empty() || res.back().X * dx < r.X * dx)
			res.push_back(r);
	}
	V = res;
}

void add_candidates(vector<int> &cand, vector<ii> &P) {
	for(auto p : P)
		cand.push_back(p.X);
}

vector<ii> solve_one_side(vector<rect> &V) {
	int L = 0, R = inf, D = 0, U = inf;
	for(auto r : V) {
		L = max(L, r.l);
		R = min(R, r.r);
		D = max(D, r.d);
		U = min(U, r.u);
	}
	
	if(L > R)
		swap(L, R);
	if(D > U)
		swap(D, U);
		
	//~ cout << L << " " << R << " " << D << " "<< U << endl;
		
	vector<ii> LU, LD, RU, RD, DU, LR;
	int minU = L, maxU = R, minD = L, maxD = R, minL = D, maxL = U, minR = D, maxR = U;
	
	rect rL(L, L, D, U), rR(R, R, D, U), rD(L, R, D, D), rU(L, R, U, U);
	
	for(auto r : V) {
		int mask = 0;
		if(rects_intersect(rL, r)) mask |= 1;
		if(rects_intersect(rR, r)) mask |= 2;
		if(rects_intersect(rD, r)) mask |= 4;
		if(rects_intersect(rU, r)) mask |= 8;
		
		if(__builtin_popcount(mask) >= 3)
			continue;
		
		if(mask == 1) {
			minL = max(minL, r.d);
			maxL = min(maxL, r.u);
		} else if(mask == 2) {
			minR = max(minR, r.d);
			maxR = min(maxR, r.u);
		} else if(mask == 4) {
			minD = max(minD, r.l);
			maxD = min(maxD, r.r);
		} else if(mask == 8) {
			minU = max(minU, r.l);
			maxU = min(maxU, r.r);
		} else if(mask == 3) {
			LR.emplace_back(r.d, r.u);
		} else if(mask == 12) {
			DU.emplace_back(r.l, r.r);
		} else if(mask == 9) {
			LU.emplace_back(r.d, r.r);
		} else if(mask == 5) {
			LD.emplace_back(r.u, r.r);
		} else if(mask == 10) {
			RU.emplace_back(r.d, r.l);
		} else if(mask == 6) {
			RD.emplace_back(r.u, r.l);
		} else
			exit(5);
	}
	
	normalise(LR, 1, 1);
	normalise(DU, 1, 1);
	normalise(LU, 1, 1);
	normalise(LD, -1, 1);
	normalise(RU, 1, -1);
	normalise(RD, -1, -1);
	
	vector<int> candL;
	
	add_candidates(candL, LR);
	add_candidates(candL, LU);
	add_candidates(candL, LD);
	candL.push_back(D);
	
	sort(candL.begin(), candL.end());
	candL.resize(distance(candL.begin(), unique(candL.begin(), candL.end())));
	
	int lstLR = -1, lstLD = LD.size() - 1, lstLU = -1, lstDU = DU.size() - 1;
	
	for(int ly : candL) {
		//~ cout << "cand " << ly << endl;
		if(ly < minL || ly > maxL)
			continue;
			
		while(lstLR + 1 < LR.size() && LR[lstLR + 1].X <= ly && ly <= LR[lstLR + 1].Y)
			lstLR++;
		while(lstLD >= 0 && LD[lstLD].X < ly)
			lstLD--;
		while(lstLU + 1 < LU.size() && LU[lstLU + 1].X <= ly)
			lstLU++;
			
		int d1 = minD;
		int d2 = min({maxD, lstLD + 1 < LD.size() ? LD[lstLD + 1].Y : inf, DU.size() ? DU[0].Y : inf});
		
		if(d1 > d2)
			continue;
			
		int dx = d2; //maleje!
		
		while(lstDU >= 0 && DU[lstDU].X > dx)
			lstDU--;
			
		int u1 = max({minU, lstDU + 1 < DU.size() ? DU.back().X : 0});
		int u2 = min({maxU, lstDU + 1 < DU.size() ? DU[lstDU + 1].Y : inf, lstLU + 1 < LU.size() ? LU[lstLU + 1].Y : inf});
		
		if(u1 > u2)
			continue;
			
		int ux = u2; // oj chyba losowo :-/
		
		//~ cout << ly << " " << dx << " " << ux << endl;
		
		int r1 = minR;
		int r2 = maxR;
		for(auto r : LR)
			if(r.Y < ly || r.X > ly)
				r1 = max(r1, r.X), r2 = min(r2, r.Y);
		for(auto r : RD)	
			if(r.X > dx)
				r2 = min(r2, r.Y);
		for(auto r : RU)
			if(r.X > ux)
				r1 = max(r1, r.Y);
				
		if(r1 > r2)
			continue;
			
		int ry = r2; // uff
		
		return {{L, ly}, {dx, D}, {R, ry}, {ux, U}};
	}
	
	return {};
}

bool check(vector<rect> &V, vector<ii> &P) {
	for(auto r : V) {
		bool ok = false;
		for(auto p : P)
			if(r.l <= p.X && p.X <= r.r && r.d <= p.Y && p.Y <= r.u)
				ok = true;
		if(!ok)
			return false;
	}
	return true;
}

vector<ii> solve(vector<rect> &V, int k) {
	int L = 0, R = inf, D = 0, U = inf;
	for(auto r : V) {
		L = max(L, r.l);
		R = min(R, r.r);
		D = max(D, r.d);
		U = min(U, r.u);
	}
	
	//~ cout << L << " " << R << " " << D << " " << U << endl;
	
	if(k == 1) {
		if(L <= R && D <= U)
			return {{L, D}};
		else 
			return {};
	}
	
	vector<ii> corners({{L, D}, {L, U}, {R, D}, {R, U}});
	for(auto c : corners) {
		vector<rect> V2;
		for(auto r : V)
			if(r.r < c.X || r.l > c.X || r.u < c.Y || r.d > c.Y)
				V2.push_back(r);
		vector<ii> r = solve(V2, k - 1);
		if(r.size()) {
			r.push_back(c);
			return r;
		}
	}
	
	vector<ii> r = solve_one_side(V);
	if(r.empty()) {
		for(auto &r : V) {
			r.u = inf-r.u;
			r.d = inf-r.d;
			swap(r.d, r.u);
		}
		r = solve_one_side(V); 
		for(auto &rr : r) {
			rr.Y = inf - rr.Y;
		}
		for(auto &r : V) {
			r.u = inf-r.u;
			r.d = inf-r.d;
			swap(r.d, r.u);
		}
	}
	
	return r;
}

int main() {
	int n, k;
	scanf("%d%d", &n, &k);
	
	vector<rect> R(n);
	for(int i = 0 ; i < n ; i++)
		scanf("%d%d%d%d", &R[i].l, &R[i].d, &R[i].r, &R[i].u);
		
	vector<ii> res = solve(R, k);
	for(auto p : res)
		printf("%d %d\n", p.X, p.Y);
		
	return 0;
}

Compilation message (stderr)

hamburg.cpp: In function 'std::vector<std::pair<int, int> > solve_one_side(std::vector<rect>&)':
hamburg.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   while(lstLR + 1 < LR.size() && LR[lstLR + 1].X <= ly && ly <= LR[lstLR + 1].Y)
      |         ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |   while(lstLU + 1 < LU.size() && LU[lstLU + 1].X <= ly)
      |         ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:142:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   int d2 = min({maxD, lstLD + 1 < LD.size() ? LD[lstLD + 1].Y : inf, DU.size() ? DU[0].Y : inf});
      |                       ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:152:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   int u1 = max({minU, lstDU + 1 < DU.size() ? DU.back().X : 0});
      |                       ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:153:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   int u2 = min({maxU, lstDU + 1 < DU.size() ? DU[lstDU + 1].Y : inf, lstLU + 1 < LU.size() ? LU[lstLU + 1].Y : inf});
      |                       ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:153:80: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   int u2 = min({maxU, lstDU + 1 < DU.size() ? DU[lstDU + 1].Y : inf, lstLU + 1 < LU.size() ? LU[lstLU + 1].Y : inf});
      |                                                                      ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:251:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  251 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:255:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  255 |   scanf("%d%d%d%d", &R[i].l, &R[i].d, &R[i].r, &R[i].u);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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