oj.uz

답안 #1050450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050450 2024-08-09T09:42:30 Z ksun69(#11101) 함박 스테이크 (JOI20_hamburg) C++17
21 / 100
 1643 ms 167712 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];
		}
	}
	vector<int> x_values, y_values;
	for(int i = 0; i < N; i++){
		x_values.push_back(S[i][0]);
		x_values.push_back(S[i][2]);
		y_values.push_back(S[i][1]);
		y_values.push_back(S[i][3]);
	}
	sort(x_values.begin(), x_values.end());
	sort(y_values.begin(), y_values.end());
	x_values.erase(unique(x_values.begin(), x_values.end()), x_values.end());
	y_values.erase(unique(y_values.begin(), y_values.end()), y_values.end());

	auto get_compress_x = [&](int x){
		return int(lower_bound(x_values.begin(), x_values.end(), x) - x_values.begin());
	};
	auto get_compress_y = [&](int y){
		return int(lower_bound(y_values.begin(), y_values.end(), y) - y_values.begin());
	};

	for(int i = 0; i < N; i++){
		S[i][0] = get_compress_x(S[i][0]);
		S[i][1] = get_compress_y(S[i][1]);
		S[i][2] = get_compress_x(S[i][2]);
		S[i][3] = get_compress_y(S[i][3]);
	}

	// 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 {int(-1e9), int(-1e9), int(1e9), 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]);
		}
		set<int> c1 = k == 1 ? set<int>({bounds[0]}) : set<int>({bounds[0], bounds[2]});
		set<int> c2 = k == 1 ? set<int>({bounds[1]}) : set<int>({bounds[1], bounds[3]});
		for(int x : c1){
			for(int y : c2){
				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 << x_values[sol[i].first] << ' ' << y_values[sol[i].second] << '\n';
		}
		exit(0);
	}
	assert(K == 4);

	vector<int> bounds {int(-1e9), int(-1e9), int(1e9), int(1e9)};
	for(int i = 0; i < N; 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]);
	}
	swap(bounds[0], bounds[2]);
	swap(bounds[1], bounds[3]);
	assert(bounds[0] < bounds[2] && bounds[1] < bounds[3]);
	for(int i = 0; i < N; i++){
		S[i][0] = max(S[i][0], bounds[0]);
		S[i][1] = max(S[i][1], bounds[1]);
		S[i][2] = min(S[i][2], bounds[2]);
		S[i][3] = min(S[i][3], bounds[3]);
	}
	vector<vector<vector<int> > > constraints(16);
	for(int i = 0; i < N; i++){
		int mask = 0;
		for(int j = 0; j < 4; j++){
			if(S[i][j] == bounds[j]) mask |= (1 << j);
		}
		constraints[mask].push_back(S[i]);
	}
	assert(constraints[0].empty());
	vector<pair<int,int> > sides(4);
	for(int b = 0; b < 4; b++){
		pair<int,int> lr = {(b & 1) ? bounds[0] : bounds[1], (b & 1) ? bounds[2] : bounds[3]};
		for(auto v : constraints[1 << b]){
			lr.first = max(lr.first, v[(b & 1) ^ 1]);
			lr.second = min(lr.second, v[(b & 1) ^ 3]);
		}
		sides[b] = lr;
	}

	auto remove_containing_rectangles = [&](vector<vector<int> > &rectangles){
		sort(rectangles.begin(), rectangles.end(), [&](vector<int> a, vector<int> b){
			return pair<int,int>(a[2] - a[0], a[3] - a[1]) < pair<int,int>(b[2] - b[0], b[3] - b[1]);
		});
		vector<vector<int> > stk;
		for(auto v : rectangles){
			if(!stk.empty() && stk.back()[0] >= v[0] && stk.back()[1] >= v[1] && stk.back()[2] <= v[2] && stk.back()[3] <= v[3]){
				continue;
			}
			stk.push_back(v);
		}
		rectangles = stk;
	};
	for(int msk = 0; msk < (1 << 4); msk++){
		remove_containing_rectangles(constraints[msk]);
	}
	vector<pair<int,int> > x_constraints, y_constraints;
	for(vector<int> c : constraints[(1 << 1) ^ (1 << 3)]){
		x_constraints.push_back({c[0], c[2]});
	}
	for(vector<int> c : constraints[(1 << 2) ^ (1 << 0)]){
		y_constraints.push_back({c[1], c[3]});
	}

	auto generate_map = [&](vector<pair<int,int> > constraints, int L, pair<int,int> l_bounds, pair<int,int> r_bounds) -> vector<pair<int,int> > {
		vector<vector<pair<int,int> > > ins(L);
		vector<vector<pair<int,int> > > rem(L);
		multiset<int> lb;
		multiset<int> ub;
		lb.insert(r_bounds.first);
		ub.insert(r_bounds.second);
		for(auto [l, r] : constraints){
			rem[l].push_back({l, r});
			ins[r].push_back({l, r});
			lb.insert(l);
			ub.insert(r);
		}
		vector<pair<int,int> > res(L);
		for(int i = 0; i < L; i++){
			for(auto [l, r] : rem[i]){
				ub.erase(ub.find(r));
				lb.erase(lb.find(l));
			}
			{
				int l = *lb.rbegin();
				int r = *ub.begin();
				if(l <= r && i >= l_bounds.first && i <= l_bounds.second){
					res[i] = {l, r};
				} else {
					res[i] = {-1, -1};
				}
			}
			for(auto [l, r] : ins[i]){
				ub.insert(r);
				lb.insert(l);
			}
		}
		for(auto [l, r] : constraints){
			lb.erase(lb.find(l));
			ub.erase(ub.find(r));
		}
		return res;
	};

	int X = x_values.size();
	int Y = y_values.size();
	vector<pair<int,int> > x_map = generate_map(x_constraints, X, sides[1], sides[3]);
	vector<pair<int,int> > y_map = generate_map(y_constraints, Y, sides[0], sides[2]);
	vector<pair<int,int> > y_map_flip = generate_map(y_constraints, Y, sides[2], sides[0]);
	int max_y_min = -1;
	for(int i = 0; i < Y; i++){
		if(y_map[i].first != -1){
			max_y_min = max(max_y_min, min(i, y_map[i].first));
		}
		if(y_map_flip[i].first != -1){
			max_y_min = max(max_y_min, min(i, y_map_flip[i].first));
		}
	}
	vector<int> y0_x3_max(Y);
	int c3 = 0;
	for(int y = 0; y < Y; y++){
		while(c3 < constraints[(1 << 0) ^ (1 << 3)].size() && constraints[(1 << 0) ^ (1 << 3)][c3][1] <= y){
			c3++;
		}
		y0_x3_max[y] = (c3 == constraints[(1 << 0) ^ (1 << 3)].size() ? bounds[2] : constraints[(1 << 0) ^ (1 << 3)][c3][2]);
	}
	vector<int> y2_x3_min(Y);
	c3 = 0;
	for(int y = 0; y < Y; y++){
		while(c3 < constraints[(1 << 2) ^ (1 << 3)].size() && constraints[(1 << 2) ^ (1 << 3)][c3][1] <= y){
			c3++;
		}
		y2_x3_min[y] = (c3 == constraints[(1 << 2) ^ (1 << 3)].size() ? bounds[0] : constraints[(1 << 2) ^ (1 << 3)][c3][0]);
	}

	int c0 = 0;
	int c2 = (int)constraints[(1 << 2) ^ (1 << 1)].size();
	vector<pair<int,int> > ans;
	for(int x = 0; x < X; x++){
		while(c0 < constraints[(1 << 0) ^ (1 << 1)].size() && constraints[(1 << 0) ^ (1 << 1)][c0][2] < x){
			c0++;
		}
		int y0max = (c0 == 0 ? bounds[3] : constraints[(1 << 0) ^ (1 << 1)][c0-1][3]);
		while(c2 > 0 && constraints[(1 << 2) ^ (1 << 1)][c2-1][0] <= x){
			c2--;
		}
		int y2max = (c2 == 0 ? bounds[3] : constraints[(1 << 2) ^ (1 << 1)][c2-1][3]);
		vector<pair<int,int> > y_pairs;
		{
			int y0 = min(y0max, max_y_min);
			if(y0 != -1){
				int y2 = min(y2max, y_map[y0].second);
				if(y_map[y0].first != -1 && y2 >= y0 && y2 >= y_map[y0].first) y_pairs.push_back({y0, y2});
			}
		}
		{
			int y2 = min(y2max, max_y_min);
			int y0 = min(y0max, y_map_flip[y2].second);
			if(y_map_flip[y2].first != -1 && y0 >= y2 && y0 >= y_map_flip[y2].first) y_pairs.push_back({y0, y2});
		}
		for(auto [y0, y2] : y_pairs){
			int xl = x_map[x].first;
			int xr = x_map[x].second;
			if(xl == -1) continue;
			assert(y0 >= sides[0].first && y0 <= sides[0].second);
			xl = max(xl, y2_x3_min[y2]);
			xr = min(xr, y0_x3_max[y0]);
			if(xl <= xr){
				ans = {{x, bounds[1]}, {xl, bounds[3]}, {bounds[0], y0}, {bounds[2], y2}};
			}
		}
	}
	if(ans.empty()){
		assert(false);
	}
	// for(int m1 = 0; m1 < 16; m1++){
	// 	for(auto cons : constraints[m1]){
	// 		bool found = false;
	// 		for(auto [x, y] : ans){
	// 			if(cons[0] <= x && x <= cons[2] && cons[1] <= y && y <= cons[3]){
	// 				found = true;
	// 			}
	// 		}
	// 		if(!found) {
	// 			cerr << m1 << ' ' << cons[0] << ' ' << cons[1] << ' ' << cons[2] << ' ' << cons[3] << '\n';
	// 			assert(false);
	// 		}
	// 	}
	// }
	// for(auto cons : S){
	// 	bool found = false;
	// 	for(auto [x, y] : ans){
	// 		if(cons[0] <= x && x <= cons[2] && cons[1] <= y && y <= cons[3]){
	// 			found = true;
	// 		}
	// 	}
	// 	if(!found) {
	// 		cerr << cons[0] << ' ' << cons[1] << ' ' << cons[2] << ' ' << cons[3] << '\n';
	// 		cerr << "bad ? " << '\n';
	// 		assert(false);
	// 	}
	// }
	for(auto [x, y] : ans){
		cout << x_values[x] << ' ' << y_values[y] << '\n';
	}
}

Compilation message

hamburg.cpp: In function 'int main()':
hamburg.cpp:215:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |   while(c3 < constraints[(1 << 0) ^ (1 << 3)].size() && constraints[(1 << 0) ^ (1 << 3)][c3][1] <= y){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:218:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  218 |   y0_x3_max[y] = (c3 == constraints[(1 << 0) ^ (1 << 3)].size() ? bounds[2] : constraints[(1 << 0) ^ (1 << 3)][c3][2]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:223:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |   while(c3 < constraints[(1 << 2) ^ (1 << 3)].size() && constraints[(1 << 2) ^ (1 << 3)][c3][1] <= y){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:226:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  226 |   y2_x3_min[y] = (c3 == constraints[(1 << 2) ^ (1 << 3)].size() ? bounds[0] : constraints[(1 << 2) ^ (1 << 3)][c3][0]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:233:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |   while(c0 < constraints[(1 << 0) ^ (1 << 1)].size() && constraints[(1 << 0) ^ (1 << 1)][c0][2] < x){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 616 KB Output is correct

Subtask #2
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 856 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 10 ms 1272 KB Output is correct
14 Correct 11 ms 1092 KB Output is correct
15 Correct 6 ms 1112 KB Output is correct
16 Correct 5 ms 1116 KB Output is correct
17 Correct 9 ms 1280 KB Output is correct
18 Correct 5 ms 1372 KB Output is correct
19 Correct 8 ms 1372 KB Output is correct
20 Correct 11 ms 1372 KB Output is correct
21 Correct 10 ms 1372 KB Output is correct
22 Correct 7 ms 1328 KB Output is correct
23 Correct 13 ms 1372 KB Output is correct
24 Correct 12 ms 1416 KB Output is correct
25 Correct 4 ms 1372 KB Output is correct
26 Correct 7 ms 1488 KB Output is correct
27 Correct 6 ms 1372 KB Output is correct
28 Correct 6 ms 1116 KB Output is correct
29 Correct 5 ms 1116 KB Output is correct
30 Correct 5 ms 1372 KB Output is correct
31 Correct 9 ms 1116 KB Output is correct
32 Correct 11 ms 1116 KB Output is correct
33 Correct 14 ms 1116 KB Output is correct
34 Correct 8 ms 1228 KB Output is correct
35 Correct 14 ms 1372 KB Output is correct
36 Correct 8 ms 1248 KB Output is correct
37 Correct 15 ms 1488 KB Output is correct
38 Correct 17 ms 1516 KB Output is correct
39 Correct 15 ms 1372 KB Output is correct
40 Correct 8 ms 1116 KB Output is correct
41 Correct 10 ms 1320 KB Output is correct
42 Correct 18 ms 1368 KB Output is correct
43 Correct 16 ms 1348 KB Output is correct
44 Correct 11 ms 1368 KB Output is correct
45 Correct 7 ms 1116 KB Output is correct
46 Correct 12 ms 1472 KB Output is correct
47 Correct 11 ms 1624 KB Output is correct
48 Correct 15 ms 1372 KB Output is correct
49 Correct 12 ms 1372 KB Output is correct
50 Correct 15 ms 1272 KB Output is correct
51 Correct 14 ms 1368 KB Output is correct
52 Correct 8 ms 1116 KB Output is correct
53 Correct 19 ms 1428 KB Output is correct
54 Correct 14 ms 1372 KB Output is correct
55 Correct 9 ms 1112 KB Output is correct
56 Correct 8 ms 1184 KB Output is correct
57 Correct 8 ms 1116 KB Output is correct
58 Correct 7 ms 1116 KB Output is correct

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Correct 190 ms 25256 KB Output is correct
6 Correct 193 ms 25264 KB Output is correct
7 Correct 206 ms 25440 KB Output is correct
8 Correct 226 ms 25440 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 856 KB Output is correct
5 Correct 224 ms 33892 KB Output is correct
6 Correct 201 ms 33632 KB Output is correct
7 Correct 202 ms 33376 KB Output is correct
8 Correct 219 ms 55900 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 199 ms 37216 KB Output is correct
14 Correct 246 ms 37780 KB Output is correct
15 Correct 215 ms 33204 KB Output is correct
16 Correct 211 ms 33708 KB Output is correct
17 Correct 237 ms 41620 KB Output is correct
18 Correct 211 ms 33112 KB Output is correct
19 Correct 205 ms 43684 KB Output is correct
20 Correct 219 ms 52136 KB Output is correct
21 Correct 417 ms 85244 KB Output is correct
22 Correct 282 ms 58220 KB Output is correct
23 Correct 282 ms 71332 KB Output is correct
24 Correct 289 ms 82008 KB Output is correct

Subtask #8
0 / 79.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 860 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 816 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 10 ms 1272 KB Output is correct
14 Correct 11 ms 1092 KB Output is correct
15 Correct 6 ms 1112 KB Output is correct
16 Correct 5 ms 1116 KB Output is correct
17 Correct 9 ms 1280 KB Output is correct
18 Correct 5 ms 1372 KB Output is correct
19 Correct 8 ms 1372 KB Output is correct
20 Correct 11 ms 1372 KB Output is correct
21 Correct 10 ms 1372 KB Output is correct
22 Correct 7 ms 1328 KB Output is correct
23 Correct 13 ms 1372 KB Output is correct
24 Correct 12 ms 1416 KB Output is correct
25 Correct 4 ms 1372 KB Output is correct
26 Correct 7 ms 1488 KB Output is correct
27 Correct 6 ms 1372 KB Output is correct
28 Correct 6 ms 1116 KB Output is correct
29 Correct 5 ms 1116 KB Output is correct
30 Correct 5 ms 1372 KB Output is correct
31 Correct 9 ms 1116 KB Output is correct
32 Correct 11 ms 1116 KB Output is correct
33 Correct 14 ms 1116 KB Output is correct
34 Correct 8 ms 1228 KB Output is correct
35 Correct 14 ms 1372 KB Output is correct
36 Correct 8 ms 1248 KB Output is correct
37 Correct 15 ms 1488 KB Output is correct
38 Correct 17 ms 1516 KB Output is correct
39 Correct 15 ms 1372 KB Output is correct
40 Correct 8 ms 1116 KB Output is correct
41 Correct 10 ms 1320 KB Output is correct
42 Correct 18 ms 1368 KB Output is correct
43 Correct 16 ms 1348 KB Output is correct
44 Correct 11 ms 1368 KB Output is correct
45 Correct 7 ms 1116 KB Output is correct
46 Correct 12 ms 1472 KB Output is correct
47 Correct 11 ms 1624 KB Output is correct
48 Correct 15 ms 1372 KB Output is correct
49 Correct 12 ms 1372 KB Output is correct
50 Correct 15 ms 1272 KB Output is correct
51 Correct 14 ms 1368 KB Output is correct
52 Correct 8 ms 1116 KB Output is correct
53 Correct 19 ms 1428 KB Output is correct
54 Correct 14 ms 1372 KB Output is correct
55 Correct 9 ms 1112 KB Output is correct
56 Correct 8 ms 1184 KB Output is correct
57 Correct 8 ms 1116 KB Output is correct
58 Correct 7 ms 1116 KB Output is correct
59 Correct 210 ms 50324 KB Output is correct
60 Correct 205 ms 41128 KB Output is correct
61 Correct 249 ms 41824 KB Output is correct
62 Correct 199 ms 39764 KB Output is correct
63 Correct 232 ms 44380 KB Output is correct
64 Correct 218 ms 34660 KB Output is correct
65 Correct 205 ms 45408 KB Output is correct
66 Correct 209 ms 44184 KB Output is correct
67 Correct 384 ms 81408 KB Output is correct
68 Correct 274 ms 69168 KB Output is correct
69 Correct 236 ms 56236 KB Output is correct
70 Correct 257 ms 76708 KB Output is correct
71 Correct 1173 ms 108196 KB Output is correct
72 Correct 1353 ms 103256 KB Output is correct
73 Correct 973 ms 101116 KB Output is correct
74 Correct 808 ms 114260 KB Output is correct
75 Correct 854 ms 88604 KB Output is correct
76 Correct 706 ms 100064 KB Output is correct
77 Correct 833 ms 104024 KB Output is correct
78 Correct 1640 ms 104964 KB Output is correct
79 Correct 878 ms 94356 KB Output is correct
80 Correct 723 ms 97436 KB Output is correct
81 Correct 1425 ms 105128 KB Output is correct
82 Correct 754 ms 98768 KB Output is correct
83 Correct 428 ms 98472 KB Output is correct
84 Correct 422 ms 69640 KB Output is correct
85 Correct 765 ms 111740 KB Output is correct
86 Correct 457 ms 83784 KB Output is correct
87 Correct 683 ms 110504 KB Output is correct
88 Correct 599 ms 109460 KB Output is correct
89 Correct 1114 ms 90448 KB Output is correct
90 Correct 1531 ms 106152 KB Output is correct
91 Correct 973 ms 82608 KB Output is correct
92 Correct 1615 ms 106692 KB Output is correct
93 Correct 1283 ms 109020 KB Output is correct
94 Correct 1548 ms 103768 KB Output is correct
95 Correct 1482 ms 102740 KB Output is correct
96 Correct 1140 ms 109536 KB Output is correct
97 Correct 1342 ms 109440 KB Output is correct
98 Correct 1245 ms 97852 KB Output is correct
99 Correct 1008 ms 105388 KB Output is correct
100 Correct 1511 ms 106932 KB Output is correct
101 Correct 1422 ms 110736 KB Output is correct
102 Correct 806 ms 77360 KB Output is correct
103 Correct 1643 ms 116240 KB Output is correct
104 Correct 949 ms 94180 KB Output is correct
105 Correct 1570 ms 114532 KB Output is correct
106 Correct 1374 ms 104420 KB Output is correct
107 Correct 1292 ms 114000 KB Output is correct
108 Correct 1435 ms 101724 KB Output is correct
109 Correct 1532 ms 106004 KB Output is correct
110 Correct 1376 ms 111008 KB Output is correct
111 Correct 1243 ms 102164 KB Output is correct
112 Correct 1480 ms 107312 KB Output is correct
113 Correct 839 ms 77344 KB Output is correct
114 Correct 796 ms 72752 KB Output is correct
115 Correct 802 ms 72892 KB Output is correct
116 Correct 789 ms 77240 KB Output is correct
117 Runtime error 876 ms 167712 KB Execution killed with signal 6
118 Halted 0 ms 0 KB -