oj.uz

답안 #220299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220299 2020-04-07T15:06:21 Z super_j6 함박 스테이크 (JOI20_hamburg) C++14
15 / 100
 436 ms 26140 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){
	 			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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 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 #2
1.0 / 1.0

# 결과 실행 시간 메모리 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
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 544 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

# 결과 실행 시간 메모리 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 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 4 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Incorrect 5 ms 1076 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 2 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 338 ms 13020 KB Output is correct
6 Correct 340 ms 13056 KB Output is correct
7 Correct 339 ms 13060 KB Output is correct
8 Correct 346 ms 12940 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 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 354 ms 14256 KB Output is correct
6 Correct 350 ms 13904 KB Output is correct
7 Correct 337 ms 14256 KB Output is correct
8 Correct 356 ms 17116 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 544 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 355 ms 14816 KB Output is correct
14 Correct 358 ms 14636 KB Output is correct
15 Correct 365 ms 12976 KB Output is correct
16 Correct 370 ms 12952 KB Output is correct
17 Correct 377 ms 16428 KB Output is correct
18 Correct 342 ms 13024 KB Output is correct
19 Correct 345 ms 17068 KB Output is correct
20 Correct 336 ms 17580 KB Output is correct
21 Correct 436 ms 26140 KB Output is correct
22 Correct 376 ms 18488 KB Output is correct
23 Correct 362 ms 21188 KB Output is correct
24 Correct 361 ms 24236 KB Output is correct

Subtask #8
0 / 79.0

# 결과 실행 시간 메모리 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 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 4 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Incorrect 5 ms 1076 KB Output isn't correct
15 Halted 0 ms 0 KB -