oj.uz

Submission #220296

# Submission time Handle Problem Language Result Execution time Memory
220296 2020-04-07T15:00:52 Z super_j6 Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 425 ms 26200 KB 
#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++){
	 	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){
	 			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.0 / 1.0

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

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

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

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 616 KB Output is correct
14 Incorrect 6 ms 1076 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 390 ms 12980 KB Output is correct
6 Correct 351 ms 12964 KB Output is correct
7 Correct 358 ms 12944 KB Output is correct
8 Correct 363 ms 13028 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 353 ms 14252 KB Output is correct
6 Correct 360 ms 13904 KB Output is correct
7 Correct 341 ms 14132 KB Output is correct
8 Correct 347 ms 17196 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 624 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 357 ms 14804 KB Output is correct
14 Correct 340 ms 14580 KB Output is correct
15 Correct 337 ms 12944 KB Output is correct
16 Correct 342 ms 12936 KB Output is correct
17 Correct 358 ms 16472 KB Output is correct
18 Correct 345 ms 13100 KB Output is correct
19 Correct 339 ms 16988 KB Output is correct
20 Correct 353 ms 17708 KB Output is correct
21 Correct 425 ms 26200 KB Output is correct
22 Correct 388 ms 18364 KB Output is correct
23 Correct 363 ms 21204 KB Output is correct
24 Correct 371 ms 24280 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 456 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 616 KB Output is correct
14 Incorrect 6 ms 1076 KB Output isn't correct
15 Halted 0 ms 0 KB -