oj.uz

답안 #220289

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220289 2020-04-07T14:27:26 Z super_j6 함박 스테이크 (JOI20_hamburg) C++14
15 / 100
 434 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[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

# 결과 실행 시간 메모리 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 488 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 4 ms 512 KB Output is correct
4 Correct 3 ms 496 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 488 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 4 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

# 결과 실행 시간 메모리 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 3 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Runtime error 6 ms 1716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 488 KB Output is correct
5 Correct 338 ms 12944 KB Output is correct
6 Correct 334 ms 12980 KB Output is correct
7 Correct 344 ms 12944 KB Output is correct
8 Correct 327 ms 12956 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 4 ms 512 KB Output is correct
4 Correct 3 ms 496 KB Output is correct
5 Correct 349 ms 14168 KB Output is correct
6 Correct 381 ms 13880 KB Output is correct
7 Correct 349 ms 14172 KB Output is correct
8 Correct 339 ms 17068 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 488 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 4 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 342 ms 14812 KB Output is correct
14 Correct 336 ms 14604 KB Output is correct
15 Correct 334 ms 13028 KB Output is correct
16 Correct 339 ms 12952 KB Output is correct
17 Correct 364 ms 16544 KB Output is correct
18 Correct 344 ms 13000 KB Output is correct
19 Correct 361 ms 16940 KB Output is correct
20 Correct 342 ms 17580 KB Output is correct
21 Correct 434 ms 26140 KB Output is correct
22 Correct 369 ms 18488 KB Output is correct
23 Correct 368 ms 21208 KB Output is correct
24 Correct 365 ms 24244 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 3 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Runtime error 6 ms 1716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -