oj.uz

Submission #220286

# Submission time Handle Problem Language Result Execution time Memory
220286 2020-04-07T14:25:26 Z super_j6 Hamburg Steak (JOI20_hamburg) C++14
2 / 100
 587 ms 72652 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.Y || 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[2] - 1, f.Y - a[i].y)].push_back(i);
		}
 	}
 	
 	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;
 			break;
 		}
 		for(int j : rot[0][it[0]]) del(j);
 	}

	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 640 KB Output is correct
3 Correct 3 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 4 ms 512 KB Output is correct

Subtask #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 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 4 ms 624 KB Output is correct
10 Incorrect 5 ms 1240 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 440 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 512 KB Output is correct
10 Runtime error 6 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #5
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 640 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 366 ms 12932 KB Output is correct
6 Runtime error 355 ms 19576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #6
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 4 ms 512 KB Output is correct
5 Incorrect 587 ms 72652 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
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 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 4 ms 624 KB Output is correct
10 Incorrect 5 ms 1240 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 440 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 512 KB Output is correct
10 Runtime error 6 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -