oj.uz

Submission #220298

# Submission time Handle Problem Language Result Execution time Memory
220298 2020-04-07T15:05:04 Z super_j6 Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 426 ms 26144 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 = 1; 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){
	 			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.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 4 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 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 3 ms 512 KB Output is correct
6 Correct 4 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 4 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 4 ms 512 KB Output is correct

Subtask #4
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 4 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 512 KB Output is correct
10 Correct 4 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 640 KB Output is correct
14 Incorrect 5 ms 1076 KB Integer parameter [name=x_1] equals to -1, violates the range [1, 10^9]
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 3 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 330 ms 12936 KB Output is correct
6 Correct 322 ms 13028 KB Output is correct
7 Correct 333 ms 12948 KB Output is correct
8 Correct 336 ms 13032 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 334 ms 14256 KB Output is correct
6 Correct 336 ms 13908 KB Output is correct
7 Correct 331 ms 14148 KB Output is correct
8 Correct 345 ms 17240 KB Output is correct

Subtask #7
6.0 / 6.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 3 ms 512 KB Output is correct
6 Correct 4 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 4 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 4 ms 512 KB Output is correct
13 Correct 336 ms 14804 KB Output is correct
14 Correct 349 ms 14636 KB Output is correct
15 Correct 347 ms 13028 KB Output is correct
16 Correct 347 ms 13028 KB Output is correct
17 Correct 373 ms 16476 KB Output is correct
18 Correct 351 ms 13048 KB Output is correct
19 Correct 353 ms 17032 KB Output is correct
20 Correct 357 ms 17628 KB Output is correct
21 Correct 426 ms 26144 KB Output is correct
22 Correct 359 ms 18440 KB Output is correct
23 Correct 373 ms 21116 KB Output is correct
24 Correct 378 ms 24236 KB Output is correct

Subtask #8
0 / 79.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 4 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 512 KB Output is correct
10 Correct 4 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 640 KB Output is correct
14 Incorrect 5 ms 1076 KB Integer parameter [name=x_1] equals to -1, violates the range [1, 10^9]
15 Halted 0 ms 0 KB -