Submission #220300

#	Time	Username	Problem	Language	Result	Execution time	Memory
220300		super_j6	Hamburg Steak (JOI20_hamburg)	C++14	100 / 100	1198 ms	111856 KiB

hamburg

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

struct rect{
	int x, y, X, Y;
};

const int maxn = 200000;
int n, m, k;
int sz[4];
int cnt[maxn];
vector<rect> a;
vector<int> id;
vector<vector<int>> rin[4], rot[4];

int idx(int x){
	return lower_bound(id.begin(), id.end(), x) - id.begin();
}

rect bnd(vector<rect> v){
	rect ret = {m, m, 0, 0};
	for(rect i : v){
		ret.x = min(ret.x, i.X);
		ret.y = min(ret.y, i.Y);
		ret.X = max(ret.X, i.x);
		ret.Y = max(ret.Y, i.y);
	}
	return ret;
}

bool crs(int a, int b, int c){
	return a <= b && b <= c;
}

vector<pi> solve(vector<rect> v, int x){
	rect f = bnd(v);
	if(x == 1){
		if(f.x < f.X || f.y < f.Y) return {};
		else return {{f.x, f.y}};
	}
	vector<pi> pt = {{f.x, f.y}, {f.x, f.Y}, {f.X, f.y}, {f.X, f.Y}};
	for(pi p : pt){
		vector<rect> nv;
		for(rect i : v){
			if(!crs(i.x, p.f, i.X) || !crs(i.y, p.s, i.Y)) nv.push_back(i);
		}
		vector<pi> ret = solve(nv, x - 1);
		if(!ret.empty()){
			ret.push_back(p);
			return ret;
		}
	}
	return {};
}

int cur;
void add(int x){
	if(!cnt[x]) cur++;
	cnt[x]++;
}

void del(int x){
	if(cnt[x] == 1) cur--;
	cnt[x]--;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	
	a.resize(n);
	for(int i = 0; i < n; i++){
		cin >> a[i].x >> a[i].y >> a[i].X >> a[i].Y;
		id.push_back(a[i].x);
		id.push_back(a[i].y);
		id.push_back(a[i].X);
		id.push_back(a[i].Y);
	}
	
	sort(id.begin(), id.end());
	id.erase(unique(id.begin(), id.end()), id.end());
	m = id.size();
	
	for(int i = 0; i < n; i++){
		a[i].x = idx(a[i].x);
		a[i].y = idx(a[i].y);
		a[i].X = idx(a[i].X);
		a[i].Y = idx(a[i].Y);
 	}
 	
 	vector<pi> ans = solve(a, k);
 	
 	if(!ans.empty()){
 		for(pi i : ans) cout << id[i.f] << " " << id[i.s] << endl;
 		return 0;
 	}
 	
 	rect f = bnd(a);
 	sz[0] = sz[2] = f.X - f.x + 1, sz[1] = sz[3] = f.Y - f.y + 1;
 	for(int i = 0; i < 4; i++){
 		rin[i].resize(sz[i]);
 		rot[i].resize(sz[i]);
 	}
 	for(int i = 0; i < n; i++){
		if(crs(a[i].y, f.y, a[i].Y)){
			rin[0][max(0, a[i].x - f.x)].push_back(i);
			rot[0][min(sz[0] - 1, a[i].X - f.x)].push_back(i);
		}
		if(crs(a[i].x, f.X, a[i].X)){
			rin[1][max(0, a[i].y - f.y)].push_back(i);
			rot[1][min(sz[1] - 1, a[i].Y - f.y)].push_back(i);
		}
		if(crs(a[i].y, f.Y, a[i].Y)){
			rin[2][max(0, f.X - a[i].X)].push_back(i);
			rot[2][min(sz[2] - 1, f.X - a[i].x)].push_back(i);
		}
		if(crs(a[i].x, f.x, a[i].X)){
			rin[3][max(0, f.Y - a[i].Y)].push_back(i);
			rot[3][min(sz[3] - 1, f.Y - a[i].y)].push_back(i);
		}
 	}
 	for(int d = 0; d < 2; d++){
 		cur = 0;
      	for(int i = 0; i < n; i++) cnt[i] = 0;
	 	for(int it[4] = {0, -1, -1, -1}; it[0] < sz[0]; it[0]++){
	 		for(int j : rin[0][it[0]]) add(j);
	 		for(int t = 1; t < 4; t++){
	 			while(it[t] < sz[t] - 1){
	 				if(it[t] != -1){
	 					bool w = 1;
	 					for(int j : rot[t][it[t]]){
	 						if(cnt[j] == 1){
	 							w = 0;
	 							break;
	 						}
	 					}
	 					if(!w) break;
	 					for(int j : rot[t][it[t]]) del(j);
	 				}
	 				it[t]++;
	 				for(int j : rin[t][it[t]]) add(j);
	 			}
	 		}
	 		if(cur == n){
	 			if(d){
	 				cout << id[f.X - it[0]] << " " << id[f.y] << endl;
		 			cout << id[f.x] << " " << id[it[1] + f.y] << endl;
		 			cout << id[it[2] + f.x] << " " << id[f.Y] << endl;
		 			cout << id[f.X] << " " << id[f.Y - it[3]] << endl;
	 			}else{
		 			cout << id[it[0] + f.x] << " " << id[f.y] << endl;
		 			cout << id[f.X] << " " << id[it[1] + f.y] << endl;
		 			cout << id[f.X - it[2]] << " " << id[f.Y] << endl;
		 			cout << id[f.x] << " " << id[f.Y - it[3]] << endl;
	 			}
	 			return 0;
	 		}
	 		for(int j : rot[0][it[0]]) del(j);
	 	}
	 	swap(rin[1], rin[3]), swap(rot[1], rot[3]);
	 	for(int t = 0; t < 4; t++){
	 		reverse(rin[t].begin(), rin[t].end());
	 		reverse(rot[t].begin(), rot[t].end());
	 		for(int i = 0; i < sz[t]; i++) swap(rin[t][i], rot[t][i]);
	 	}
 	}
 	
 	cout << -1 << endl;

	return 0;
}

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