oj.uz

Submission #220208

# Submission time Handle Problem Language Result Execution time Memory
220208 2020-04-07T10:30:54 Z super_j6 Hamburg Steak (JOI20_hamburg) C++14
6 / 100
 1205 ms 21684 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define pi pair<int, int>
#define f first
#define s second

const int inf = 1000000007;
const int maxn = 200000;
int n, k;
int x[maxn], X[maxn], y[maxn], Y[maxn];
vector<int> a;

vector<pi> solve(vector<int> v, int z){
	if(!z && !v.empty()) return vector<pi>(1, {0, 0});
	if(v.empty()) return vector<pi>(1, {-1, -1});
	
	for(int h = 0; h < 2; h++){
		for(int g = 0; g < 2; g++){
			int mn = inf;
			for(int i : v) mn = min(mn, X[i]);
			
			vector<pi> p;
			for(int i : v){
				p.push_back({y[i], i});
				p.push_back({Y[i], i});
			}
			sort(p.begin(), p.end());
			for(int t = 0; t < 2; t++){
				bool f = 0;
				set<int> cur;
				for(pi i : p){
					f |= X[i.s] == mn;
					if(cur.find(i.s) == cur.end()){
						cur.insert(i.s);
					}else{
						if(f){
							vector<int> nv;
							for(int j : v){
								if(x[j] > mn || y[j] > i.f || Y[j] < i.f) nv.push_back(j);
							}
							if(g) for(int i = 0; i < n; i++) swap(x[i], y[i]), swap(X[i], Y[i]);
							if(h) for(int i = 0; i < n; i++) x[i] *= -1, y[i] *= -1, X[i] *= -1, Y[i] *= -1;
							vector<pi> ans = solve(nv, z - 1);
							if(g) for(int i = 0; i < n; i++) swap(x[i], y[i]), swap(X[i], Y[i]);
							if(h) for(int i = 0; i < n; i++) x[i] *= -1, y[i] *= -1, X[i] *= -1, Y[i] *= -1;
							if(ans[0].f){
								ans.push_back({mn, i.f});
								if(g) swap(ans.back().f, ans.back().s);
								if(h) ans.back().f *= -1, ans.back().s *= -1;
								return ans;
							}
							break;
						}else{
							cur.erase(i.s);
						}
					}
				}
				reverse(p.begin(), p.end());
			}
			for(int i = 0; i < n; i++) swap(x[i], y[i]), swap(X[i], Y[i]);
		}
		for(int i = 0; i < n; i++) x[i] *= -1, y[i] *= -1, X[i] *= -1, Y[i] *= -1;
	}
	
	return vector<pi>(1, {0, 0});
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	
	a.resize(n);
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i] >> X[i] >> Y[i];
		a[i] = i;
	}
	
	vector<pi> ans = solve(a, k);
	
	for(int i = 1; i <= k; i++){
		if(i < ans.size()) cout << ans[i].f << " " << ans[i].s << endl;
		else cout << 69 << " " << 420 << endl;
	} 

	return 0;
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:88:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   if(i < ans.size()) cout << ans[i].f << " " << ans[i].s << endl;
      |      ~~^~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 488 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 628 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 26 ms 640 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Incorrect 245 ms 876 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 64 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Incorrect 1174 ms 984 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 488 KB Output is correct
5 Correct 357 ms 17504 KB Output is correct
6 Correct 303 ms 17508 KB Output is correct
7 Correct 295 ms 17528 KB Output is correct
8 Correct 310 ms 17588 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 6 ms 628 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 318 ms 20964 KB Output is correct
6 Correct 608 ms 20940 KB Output is correct
7 Correct 283 ms 19540 KB Output is correct
8 Correct 1205 ms 21684 KB Output is correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 26 ms 640 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Incorrect 245 ms 876 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 640 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 64 ms 640 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Incorrect 1174 ms 984 KB Output isn't correct
10 Halted 0 ms 0 KB -