oj.uz

Submission #1050023

# Submission time Handle Problem Language Result Execution time Memory
1050023 2024-08-09T06:55:40 Z ksun69(#11101) Hamburg Steak (JOI20_hamburg) C++17
2 / 100
 100 ms 45564 KB 
#include <bits/stdc++.h>
using namespace std;

namespace std {

template<class Fun>
class y_combinator_result {
	Fun fun_;
public:
	template<class T>
	explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
	decltype(auto) operator()(Args &&...args) {
		return fun_(std::ref(*this), std::forward<Args>(args)...);
	}
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
	return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

} // namespace std

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, K;
	cin >> N >> K;
	vector<vector<int> > S(N, vector<int>(4));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < 4; j++){
			cin >> S[i][j];
		}
	}
	// L D R U
	vector<pair<int,int> > bad = {{-1, -1}};
	auto sol = y_combinator([&](auto self, vector<vector<int>> s, int k) -> vector<pair<int,int> > {
		if(s.size() == 0) return vector<pair<int,int> >(k, {0, 0});
		if(k == 0) return bad;
		vector<int> bounds {0, int(1e9), 0, int(1e9)};
		for(int i = 0; i < (int)s.size(); i++){
			bounds[0] = max(bounds[0], s[i][0]);
			bounds[1] = max(bounds[1], s[i][1]);
			bounds[2] = min(bounds[2], s[i][2]);
			bounds[3] = min(bounds[3], s[i][3]);
		}
		for(int x : {bounds[0], bounds[2]}){
			for(int y : {bounds[1], bounds[3]}){
				vector<vector<int> > nxt;
				for(int i = 0; i < (int)s.size(); i++){
					if(!(s[i][0] <= x && s[i][2] >= x && s[i][1] <= y && s[i][3] >= y)) nxt.push_back(s[i]);
				}
				auto res = self(nxt, k-1);
				if(res != bad) {
					res.push_back({x, y});
					return res;
				}
			}
		}
		return bad;
	})(S, K);
	if(sol != bad){
		for(int i = 0; i < K; i++){
			cout << sol[i].first << ' ' << sol[i].second << '\n';
		}
	} else {
		assert(false);
	}
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct

Subtask #2
0 / 1.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1300 KB Output is correct
2 Correct 6 ms 1116 KB Output is correct
3 Correct 4 ms 1112 KB Output is correct
4 Correct 2 ms 1292 KB Output is correct
5 Correct 3 ms 1368 KB Output is correct
6 Correct 3 ms 1316 KB Output is correct
7 Runtime error 11 ms 2336 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1372 KB Output is correct
2 Correct 9 ms 1384 KB Output is correct
3 Correct 9 ms 1520 KB Output is correct
4 Correct 10 ms 1524 KB Output is correct
5 Correct 10 ms 1548 KB Output is correct
6 Correct 9 ms 1540 KB Output is correct
7 Runtime error 38 ms 2644 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 73 ms 44600 KB Output is correct
6 Correct 72 ms 44284 KB Output is correct
7 Correct 78 ms 44360 KB Output is correct
8 Correct 100 ms 45564 KB Output is correct

Subtask #6
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1300 KB Output is correct
2 Correct 6 ms 1116 KB Output is correct
3 Correct 4 ms 1112 KB Output is correct
4 Correct 2 ms 1292 KB Output is correct
5 Correct 3 ms 1368 KB Output is correct
6 Correct 3 ms 1316 KB Output is correct
7 Runtime error 11 ms 2336 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1372 KB Output is correct
2 Correct 9 ms 1384 KB Output is correct
3 Correct 9 ms 1520 KB Output is correct
4 Correct 10 ms 1524 KB Output is correct
5 Correct 10 ms 1548 KB Output is correct
6 Correct 9 ms 1540 KB Output is correct
7 Runtime error 38 ms 2644 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -