oj.uz

Submission #220260

# Submission time Handle Problem Language Result Execution time Memory
220260 2020-04-07T12:53:13 Z super_j6 Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 420 ms 24180 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;
vector<rect> a;
vector<int> id;

int idx(int x){
	return lower_bound(id.begin(), id.end(), x) - id.begin();
}

rect bnd(vector<rect> v){
	rect ret = {0, 0, m, m};
	for(rect i : v){
		ret.x = max(ret.x, i.x);
		ret.y = max(ret.y, i.y);
		ret.X = min(ret.X, i.X);
		ret.Y = min(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 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;
 	}

	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 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 516 KB Output is correct
3 Correct 4 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 472 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 520 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 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 4 ms 512 KB Output is correct
8 Correct 4 ms 680 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 656 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Incorrect 4 ms 640 KB Unexpected end of file - int32 expected
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 3 ms 512 KB Output is correct
5 Correct 344 ms 13004 KB Output is correct
6 Correct 337 ms 12976 KB Output is correct
7 Correct 320 ms 13028 KB Output is correct
8 Correct 340 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 516 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 338 ms 14896 KB Output is correct
6 Correct 343 ms 15296 KB Output is correct
7 Correct 339 ms 14512 KB Output is correct
8 Correct 368 ms 16812 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 472 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 520 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 348 ms 15792 KB Output is correct
14 Correct 373 ms 15532 KB Output is correct
15 Correct 347 ms 16556 KB Output is correct
16 Correct 333 ms 13908 KB Output is correct
17 Correct 340 ms 15644 KB Output is correct
18 Correct 333 ms 13032 KB Output is correct
19 Correct 346 ms 16028 KB Output is correct
20 Correct 420 ms 24180 KB Output is correct
21 Correct 342 ms 16980 KB Output is correct
22 Correct 368 ms 22576 KB Output is correct
23 Correct 373 ms 22124 KB Output is correct
24 Correct 357 ms 22416 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 4 ms 512 KB Output is correct
8 Correct 4 ms 680 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 4 ms 656 KB Output is correct
12 Correct 3 ms 620 KB Output is correct
13 Correct 3 ms 512 KB Output is correct
14 Incorrect 4 ms 640 KB Unexpected end of file - int32 expected
15 Halted 0 ms 0 KB -