oj.uz

답안 #1050528

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050528 2024-08-09T10:30:39 Z ksun69(#11101) 함박 스테이크 (JOI20_hamburg) C++17
100 / 100
 1149 ms 103060 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]);
		}
		if(k == 1){
			if(bounds[2] <= bounds[0] || bounds[3] <= bounds[1]) return bad;
			return vector<pair<int,int> >(1, {bounds[0], bounds[1]});
		}
		set<int> c1 = set<int>({bounds[0], bounds[2]});
		set<int> c2 = 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 = Y-1;
	for(auto cons : y_constraints){
		max_y_min = min(max_y_min, cons.second);
	}
	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(sides[0].second, 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(sides[2].second, 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:214:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |   while(c3 < constraints[(1 << 0) ^ (1 << 3)].size() && constraints[(1 << 0) ^ (1 << 3)][c3][1] <= y){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:217:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |   y0_x3_max[y] = (c3 == constraints[(1 << 0) ^ (1 << 3)].size() ? bounds[2] : constraints[(1 << 0) ^ (1 << 3)][c3][2]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:222:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |   while(c3 < constraints[(1 << 2) ^ (1 << 3)].size() && constraints[(1 << 2) ^ (1 << 3)][c3][1] <= y){
      |         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:225:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  225 |   y2_x3_min[y] = (c3 == constraints[(1 << 2) ^ (1 << 3)].size() ? bounds[0] : constraints[(1 << 2) ^ (1 << 3)][c3][0]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
hamburg.cpp:232:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  232 |   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 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 636 KB Output is correct
4 Correct 1 ms 604 KB Output is correct

Subtask #2
1.0 / 1.0

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

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 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 3 ms 1116 KB Output is correct

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 856 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 856 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 6 ms 1256 KB Output is correct
14 Correct 10 ms 1112 KB Output is correct
15 Correct 8 ms 1112 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 8 ms 1208 KB Output is correct
18 Correct 6 ms 1116 KB Output is correct
19 Correct 7 ms 1308 KB Output is correct
20 Correct 8 ms 1116 KB Output is correct
21 Correct 7 ms 1372 KB Output is correct
22 Correct 5 ms 1396 KB Output is correct
23 Correct 9 ms 1368 KB Output is correct
24 Correct 9 ms 1336 KB Output is correct
25 Correct 3 ms 1156 KB Output is correct
26 Correct 6 ms 1372 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 3 ms 860 KB Output is correct
29 Correct 3 ms 1128 KB Output is correct
30 Correct 3 ms 1116 KB Output is correct
31 Correct 7 ms 1116 KB Output is correct
32 Correct 9 ms 1208 KB Output is correct
33 Correct 7 ms 1168 KB Output is correct
34 Correct 10 ms 1160 KB Output is correct
35 Correct 12 ms 1344 KB Output is correct
36 Correct 10 ms 1116 KB Output is correct
37 Correct 11 ms 1360 KB Output is correct
38 Correct 19 ms 1372 KB Output is correct
39 Correct 8 ms 1116 KB Output is correct
40 Correct 7 ms 1208 KB Output is correct
41 Correct 8 ms 1236 KB Output is correct
42 Correct 14 ms 1112 KB Output is correct
43 Correct 8 ms 1200 KB Output is correct
44 Correct 11 ms 1424 KB Output is correct
45 Correct 4 ms 1116 KB Output is correct
46 Correct 13 ms 1372 KB Output is correct
47 Correct 8 ms 1148 KB Output is correct
48 Correct 10 ms 1372 KB Output is correct
49 Correct 9 ms 1236 KB Output is correct
50 Correct 7 ms 1116 KB Output is correct
51 Correct 10 ms 1392 KB Output is correct
52 Correct 9 ms 1312 KB Output is correct
53 Correct 9 ms 1308 KB Output is correct
54 Correct 10 ms 1372 KB Output is correct
55 Correct 11 ms 1112 KB Output is correct
56 Correct 7 ms 1184 KB Output is correct
57 Correct 6 ms 1112 KB Output is correct
58 Correct 11 ms 1212 KB Output is correct

Subtask #5
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 636 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 199 ms 29476 KB Output is correct
6 Correct 197 ms 29372 KB Output is correct
7 Correct 202 ms 29788 KB Output is correct
8 Correct 197 ms 29544 KB Output is correct

Subtask #6
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 2 ms 952 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 209 ms 38148 KB Output is correct
6 Correct 205 ms 37188 KB Output is correct
7 Correct 203 ms 37724 KB Output is correct
8 Correct 221 ms 48984 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 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 3 ms 1116 KB Output is correct
13 Correct 213 ms 41576 KB Output is correct
14 Correct 208 ms 42192 KB Output is correct
15 Correct 200 ms 37476 KB Output is correct
16 Correct 200 ms 38100 KB Output is correct
17 Correct 209 ms 46292 KB Output is correct
18 Correct 206 ms 37480 KB Output is correct
19 Correct 210 ms 48016 KB Output is correct
20 Correct 220 ms 50452 KB Output is correct
21 Correct 360 ms 75512 KB Output is correct
22 Correct 274 ms 53024 KB Output is correct
23 Correct 253 ms 64144 KB Output is correct
24 Correct 279 ms 70804 KB Output is correct

Subtask #8
79.0 / 79.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 860 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 856 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 856 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 6 ms 1256 KB Output is correct
14 Correct 10 ms 1112 KB Output is correct
15 Correct 8 ms 1112 KB Output is correct
16 Correct 4 ms 1116 KB Output is correct
17 Correct 8 ms 1208 KB Output is correct
18 Correct 6 ms 1116 KB Output is correct
19 Correct 7 ms 1308 KB Output is correct
20 Correct 8 ms 1116 KB Output is correct
21 Correct 7 ms 1372 KB Output is correct
22 Correct 5 ms 1396 KB Output is correct
23 Correct 9 ms 1368 KB Output is correct
24 Correct 9 ms 1336 KB Output is correct
25 Correct 3 ms 1156 KB Output is correct
26 Correct 6 ms 1372 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 3 ms 860 KB Output is correct
29 Correct 3 ms 1128 KB Output is correct
30 Correct 3 ms 1116 KB Output is correct
31 Correct 7 ms 1116 KB Output is correct
32 Correct 9 ms 1208 KB Output is correct
33 Correct 7 ms 1168 KB Output is correct
34 Correct 10 ms 1160 KB Output is correct
35 Correct 12 ms 1344 KB Output is correct
36 Correct 10 ms 1116 KB Output is correct
37 Correct 11 ms 1360 KB Output is correct
38 Correct 19 ms 1372 KB Output is correct
39 Correct 8 ms 1116 KB Output is correct
40 Correct 7 ms 1208 KB Output is correct
41 Correct 8 ms 1236 KB Output is correct
42 Correct 14 ms 1112 KB Output is correct
43 Correct 8 ms 1200 KB Output is correct
44 Correct 11 ms 1424 KB Output is correct
45 Correct 4 ms 1116 KB Output is correct
46 Correct 13 ms 1372 KB Output is correct
47 Correct 8 ms 1148 KB Output is correct
48 Correct 10 ms 1372 KB Output is correct
49 Correct 9 ms 1236 KB Output is correct
50 Correct 7 ms 1116 KB Output is correct
51 Correct 10 ms 1392 KB Output is correct
52 Correct 9 ms 1312 KB Output is correct
53 Correct 9 ms 1308 KB Output is correct
54 Correct 10 ms 1372 KB Output is correct
55 Correct 11 ms 1112 KB Output is correct
56 Correct 7 ms 1184 KB Output is correct
57 Correct 6 ms 1112 KB Output is correct
58 Correct 11 ms 1212 KB Output is correct
59 Correct 213 ms 55052 KB Output is correct
60 Correct 224 ms 45704 KB Output is correct
61 Correct 231 ms 47436 KB Output is correct
62 Correct 208 ms 44280 KB Output is correct
63 Correct 211 ms 48480 KB Output is correct
64 Correct 205 ms 39008 KB Output is correct
65 Correct 218 ms 49764 KB Output is correct
66 Correct 213 ms 47828 KB Output is correct
67 Correct 310 ms 76396 KB Output is correct
68 Correct 256 ms 63836 KB Output is correct
69 Correct 232 ms 55876 KB Output is correct
70 Correct 252 ms 71004 KB Output is correct
71 Correct 833 ms 98620 KB Output is correct
72 Correct 1002 ms 94724 KB Output is correct
73 Correct 751 ms 93128 KB Output is correct
74 Correct 615 ms 97488 KB Output is correct
75 Correct 731 ms 81452 KB Output is correct
76 Correct 519 ms 87192 KB Output is correct
77 Correct 621 ms 91100 KB Output is correct
78 Correct 1102 ms 98204 KB Output is correct
79 Correct 657 ms 87200 KB Output is correct
80 Correct 591 ms 92764 KB Output is correct
81 Correct 979 ms 92272 KB Output is correct
82 Correct 517 ms 84480 KB Output is correct
83 Correct 407 ms 89936 KB Output is correct
84 Correct 341 ms 64392 KB Output is correct
85 Correct 525 ms 96340 KB Output is correct
86 Correct 369 ms 77912 KB Output is correct
87 Correct 483 ms 94068 KB Output is correct
88 Correct 437 ms 91608 KB Output is correct
89 Correct 824 ms 85332 KB Output is correct
90 Correct 1149 ms 95476 KB Output is correct
91 Correct 772 ms 83364 KB Output is correct
92 Correct 1139 ms 103060 KB Output is correct
93 Correct 987 ms 96792 KB Output is correct
94 Correct 1111 ms 92388 KB Output is correct
95 Correct 1092 ms 95752 KB Output is correct
96 Correct 839 ms 94464 KB Output is correct
97 Correct 951 ms 93644 KB Output is correct
98 Correct 944 ms 89056 KB Output is correct
99 Correct 830 ms 93596 KB Output is correct
100 Correct 1098 ms 94896 KB Output is correct
101 Correct 1051 ms 95464 KB Output is correct
102 Correct 671 ms 81372 KB Output is correct
103 Correct 1136 ms 99036 KB Output is correct
104 Correct 797 ms 88240 KB Output is correct
105 Correct 1116 ms 99924 KB Output is correct
106 Correct 1018 ms 95972 KB Output is correct
107 Correct 931 ms 96124 KB Output is correct
108 Correct 1067 ms 94024 KB Output is correct
109 Correct 1101 ms 97020 KB Output is correct
110 Correct 1067 ms 96360 KB Output is correct
111 Correct 1004 ms 86348 KB Output is correct
112 Correct 1108 ms 98964 KB Output is correct
113 Correct 754 ms 78320 KB Output is correct
114 Correct 750 ms 73828 KB Output is correct
115 Correct 754 ms 78252 KB Output is correct
116 Correct 754 ms 78308 KB Output is correct
117 Correct 730 ms 86740 KB Output is correct
118 Correct 749 ms 86820 KB Output is correct
119 Correct 739 ms 87728 KB Output is correct
120 Correct 734 ms 88416 KB Output is correct
121 Correct 781 ms 87984 KB Output is correct
122 Correct 724 ms 87144 KB Output is correct
123 Correct 735 ms 87704 KB Output is correct
124 Correct 743 ms 88436 KB Output is correct
125 Correct 786 ms 86496 KB Output is correct
126 Correct 768 ms 86220 KB Output is correct