oj.uz

답안 #574357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
574357 2022-06-08T11:43:37 Z wjajjsasqq 분수 공원 (IOI21_parks) C++17
70 / 100
 522 ms 149872 KB 
#include "parks.h"
#include <cstdio>
#include <cstring>
#include <algorithm>

struct point {
	int x, y, ind;
};

struct bench {
	int x, y, dir;
};

bool operator<(point a, point b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}

bool operator<(bench a, bench b) {
	if (a.x == b.x) {
		if (a.y == b.y) return a.dir < b.dir;
		return a.y < b.y;
	}
	return a.x < b.x;
}

bool operator==(bench a, bench b) {
	return !(a < b) && !(b < a);
}

const int N = 200005;
const int V = N * 4;
int n, e1[N * 2], e2[N * 2], ord[V], vis[V];
bool u[N];
std::vector<std::pair<int, int> > edg;
std::vector<int> g[V], t[V];
point a[N];
bench b1[N], b2[N];
std::vector<bench> ball;

int dx[] = {-1, 1, 0, 0}, dx1[] = {-1, 1, -1, 1};
int dy[] = {0, 0, -1, 1}, dy1[] = {-1, -1, 1, 1};

int locate(point p) {
	int pos = std::lower_bound(a, a + n, p) - a;
	if (pos < n && a[pos].x == p.x && a[pos].y == p.y) return pos;
	return -1;
}

void dfs(int ind) {
	u[ind] = 1;
	for (int i = 0; i < 4; ++i) {
		int next = locate({a[ind].x + dx[i] * 2, a[ind].y + dy[i] * 2});
		if (next != -1 && !u[next]) {
			edg.push_back(std::make_pair(ind, next));
			dfs(next);
		}
	}
}

void add_edge(int a, int b) {
	g[a].push_back(b);
	t[b].push_back(a);
	g[b ^ 1].push_back(a ^ 1);
	t[a ^ 1].push_back(b ^ 1);
}

void dfs0(int v) {
	static int dt = 0;
	vis[v] = 1;
	for (int i = 0; i < (int)g[v].size(); ++i) if (!vis[g[v][i]]) dfs0(g[v][i]);
	ord[dt++] = v;
}

int cmp;
void dfs1(int v) {
	vis[v] = cmp;
	for (int i = 0; i < (int)t[v].size(); ++i) if (!vis[t[v][i]]) dfs1(t[v][i]);
}

bool yes(int i) {
	return vis[i << 1 | 1] > vis[i << 1];
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	n = x.size();
	for (int i = 0; i < n; ++i) {
		a[i].x = x[i];
		a[i].y = y[i];
		a[i].ind = i;
	}
	std::sort(a, a + n);
	dfs(0);
	for (int i = 0; i < n; ++i) if (!u[i]) return 0;
	for (int i = 0; i < (int)edg.size(); ++i) {
		//printf("%d %d %d %d\n", a[edg[i].first].x, a[edg[i].first].y, a[edg[i].second].x, a[edg[i].second].y);
		if (a[edg[i].first].x == a[edg[i].second].x) {
			int mean = a[edg[i].first].y + a[edg[i].second].y >> 1;
			b1[i].x = a[edg[i].first].x - 1;
			b2[i].x = a[edg[i].first].x + 1;
			b1[i].y = b2[i].y = mean;
			b1[i].dir = 1;
			b2[i].dir = 3;
		} else {
			int mean = a[edg[i].first].x + a[edg[i].second].x >> 1;
			b1[i].x = b2[i].x = mean;
			b1[i].y = a[edg[i].first].y - 1;
			b2[i].y = a[edg[i].first].y + 1;
			b1[i].dir = 0;
			b2[i].dir = 2;
		}
		ball.push_back(b1[i]);
		ball.push_back(b2[i]);
	}
	std::sort(ball.begin(), ball.end());
	ball.resize(std::unique(ball.begin(), ball.end()) - ball.begin());
	for (int i = 0; i < (int)ball.size();) {
		int j = i;
		do {
			//printf("%d %d %d\n", ball[i].x, ball[i].y, ball[i].dir);
			++i;
		} while (i < (int)ball.size() && ball[i].x == ball[i - 1].x && ball[i].y == ball[i - 1].y);
		while (j < i) {
			for (int k = j + 1; k < i; ++k) add_edge(j << 1 | 1, k << 1);
			++j;
		}
	}
	for (int i = 0; i < (int)edg.size(); ++i) {
		e1[i] = std::lower_bound(ball.begin(), ball.end(), b1[i]) - ball.begin();
		e2[i] = std::lower_bound(ball.begin(), ball.end(), b2[i]) - ball.begin();
		add_edge(e1[i] << 1, e2[i] << 1 | 1);
	}
	for (int i = 0; i < ball.size() * 2; ++i) if (!vis[i]) dfs0(i);
	memset(vis, 0, sizeof vis);
	for (int i = (int)ball.size() * 2 - 1; i >= 0; --i) if (!vis[ord[i]]) {
		++cmp;
		dfs1(ord[i]);
	}
	for (int i = 0; i < (int)ball.size(); ++i) if (vis[i << 1] == vis[i << 1 | 1]) return 0;
	std::vector<int> ansu(edg.size()), ansv(edg.size()), ansa(edg.size()), ansb(edg.size());
	for (int i = 0; i < (int)edg.size(); ++i) {
		ansu[i] = a[edg[i].first].ind;
		ansv[i] = a[edg[i].second].ind;
		if (yes(e1[i])) {
			ansa[i] = ball[e1[i]].x;
			ansb[i] = ball[e1[i]].y;
		} else {
			ansa[i] = ball[e2[i]].x;
			ansb[i] = ball[e2[i]].y;
		}
	}
	build(ansu, ansv, ansa, ansb);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:98:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |    int mean = a[edg[i].first].y + a[edg[i].second].y >> 1;
      |               ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:105:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |    int mean = a[edg[i].first].x + a[edg[i].second].x >> 1;
      |               ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
parks.cpp:133:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<bench>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |  for (int i = 0; i < ball.size() * 2; ++i) if (!vis[i]) dfs0(i);
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 40940 KB Output is correct
2 Correct 19 ms 40956 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 21 ms 40916 KB Output is correct
5 Correct 22 ms 41024 KB Output is correct
6 Correct 23 ms 37792 KB Output is correct
7 Correct 19 ms 37844 KB Output is correct
8 Correct 20 ms 37880 KB Output is correct
9 Correct 180 ms 81116 KB Output is correct
10 Correct 37 ms 45028 KB Output is correct
11 Correct 91 ms 62564 KB Output is correct
12 Correct 39 ms 47056 KB Output is correct
13 Correct 33 ms 42712 KB Output is correct
14 Correct 20 ms 37928 KB Output is correct
15 Correct 19 ms 37972 KB Output is correct
16 Correct 181 ms 81148 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 40940 KB Output is correct
2 Correct 19 ms 40956 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 21 ms 40916 KB Output is correct
5 Correct 22 ms 41024 KB Output is correct
6 Correct 23 ms 37792 KB Output is correct
7 Correct 19 ms 37844 KB Output is correct
8 Correct 20 ms 37880 KB Output is correct
9 Correct 180 ms 81116 KB Output is correct
10 Correct 37 ms 45028 KB Output is correct
11 Correct 91 ms 62564 KB Output is correct
12 Correct 39 ms 47056 KB Output is correct
13 Correct 33 ms 42712 KB Output is correct
14 Correct 20 ms 37928 KB Output is correct
15 Correct 19 ms 37972 KB Output is correct
16 Correct 181 ms 81148 KB Output is correct
17 Correct 22 ms 40916 KB Output is correct
18 Correct 19 ms 41044 KB Output is correct
19 Correct 19 ms 40952 KB Output is correct
20 Correct 21 ms 41016 KB Output is correct
21 Correct 21 ms 37880 KB Output is correct
22 Correct 19 ms 40948 KB Output is correct
23 Correct 426 ms 141740 KB Output is correct
24 Correct 21 ms 40952 KB Output is correct
25 Correct 22 ms 41548 KB Output is correct
26 Correct 22 ms 38056 KB Output is correct
27 Correct 25 ms 37992 KB Output is correct
28 Correct 194 ms 81140 KB Output is correct
29 Correct 257 ms 101440 KB Output is correct
30 Correct 340 ms 121620 KB Output is correct
31 Correct 426 ms 141800 KB Output is correct
32 Correct 24 ms 41044 KB Output is correct
33 Correct 20 ms 40948 KB Output is correct
34 Correct 20 ms 40936 KB Output is correct
35 Correct 20 ms 37840 KB Output is correct
36 Correct 19 ms 37804 KB Output is correct
37 Correct 20 ms 40916 KB Output is correct
38 Correct 22 ms 40976 KB Output is correct
39 Correct 25 ms 40916 KB Output is correct
40 Correct 24 ms 40924 KB Output is correct
41 Correct 21 ms 37844 KB Output is correct
42 Correct 22 ms 40980 KB Output is correct
43 Correct 19 ms 37988 KB Output is correct
44 Correct 19 ms 37972 KB Output is correct
45 Correct 199 ms 87428 KB Output is correct
46 Correct 294 ms 108428 KB Output is correct
47 Correct 298 ms 108408 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 40940 KB Output is correct
2 Correct 19 ms 40956 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 21 ms 40916 KB Output is correct
5 Correct 22 ms 41024 KB Output is correct
6 Correct 23 ms 37792 KB Output is correct
7 Correct 19 ms 37844 KB Output is correct
8 Correct 20 ms 37880 KB Output is correct
9 Correct 180 ms 81116 KB Output is correct
10 Correct 37 ms 45028 KB Output is correct
11 Correct 91 ms 62564 KB Output is correct
12 Correct 39 ms 47056 KB Output is correct
13 Correct 33 ms 42712 KB Output is correct
14 Correct 20 ms 37928 KB Output is correct
15 Correct 19 ms 37972 KB Output is correct
16 Correct 181 ms 81148 KB Output is correct
17 Correct 22 ms 40916 KB Output is correct
18 Correct 19 ms 41044 KB Output is correct
19 Correct 19 ms 40952 KB Output is correct
20 Correct 21 ms 41016 KB Output is correct
21 Correct 21 ms 37880 KB Output is correct
22 Correct 19 ms 40948 KB Output is correct
23 Correct 426 ms 141740 KB Output is correct
24 Correct 21 ms 40952 KB Output is correct
25 Correct 22 ms 41548 KB Output is correct
26 Correct 22 ms 38056 KB Output is correct
27 Correct 25 ms 37992 KB Output is correct
28 Correct 194 ms 81140 KB Output is correct
29 Correct 257 ms 101440 KB Output is correct
30 Correct 340 ms 121620 KB Output is correct
31 Correct 426 ms 141800 KB Output is correct
32 Correct 24 ms 41044 KB Output is correct
33 Correct 20 ms 40948 KB Output is correct
34 Correct 20 ms 40936 KB Output is correct
35 Correct 20 ms 37840 KB Output is correct
36 Correct 19 ms 37804 KB Output is correct
37 Correct 20 ms 40916 KB Output is correct
38 Correct 22 ms 40976 KB Output is correct
39 Correct 25 ms 40916 KB Output is correct
40 Correct 24 ms 40924 KB Output is correct
41 Correct 21 ms 37844 KB Output is correct
42 Correct 22 ms 40980 KB Output is correct
43 Correct 19 ms 37988 KB Output is correct
44 Correct 19 ms 37972 KB Output is correct
45 Correct 199 ms 87428 KB Output is correct
46 Correct 294 ms 108428 KB Output is correct
47 Correct 298 ms 108408 KB Output is correct
48 Correct 20 ms 41044 KB Output is correct
49 Correct 23 ms 41044 KB Output is correct
50 Correct 20 ms 40948 KB Output is correct
51 Correct 23 ms 40952 KB Output is correct
52 Correct 20 ms 41044 KB Output is correct
53 Correct 23 ms 40944 KB Output is correct
54 Correct 22 ms 40940 KB Output is correct
55 Correct 491 ms 143844 KB Output is correct
56 Correct 23 ms 40908 KB Output is correct
57 Correct 26 ms 41932 KB Output is correct
58 Correct 38 ms 44016 KB Output is correct
59 Correct 23 ms 38400 KB Output is correct
60 Correct 230 ms 92264 KB Output is correct
61 Correct 317 ms 110236 KB Output is correct
62 Correct 395 ms 125996 KB Output is correct
63 Correct 473 ms 143940 KB Output is correct
64 Correct 20 ms 37844 KB Output is correct
65 Correct 20 ms 40932 KB Output is correct
66 Correct 20 ms 37896 KB Output is correct
67 Correct 320 ms 123036 KB Output is correct
68 Correct 308 ms 112096 KB Output is correct
69 Correct 306 ms 117256 KB Output is correct
70 Correct 21 ms 38100 KB Output is correct
71 Correct 24 ms 38276 KB Output is correct
72 Correct 249 ms 85708 KB Output is correct
73 Correct 338 ms 108532 KB Output is correct
74 Correct 469 ms 131008 KB Output is correct
75 Correct 446 ms 133580 KB Output is correct
76 Correct 348 ms 123000 KB Output is correct
77 Correct 21 ms 38228 KB Output is correct
78 Correct 27 ms 38352 KB Output is correct
79 Correct 232 ms 86800 KB Output is correct
80 Correct 348 ms 109936 KB Output is correct
81 Correct 454 ms 132944 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 40940 KB Output is correct
2 Correct 19 ms 40956 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 21 ms 40916 KB Output is correct
5 Correct 22 ms 41024 KB Output is correct
6 Correct 23 ms 37792 KB Output is correct
7 Correct 19 ms 37844 KB Output is correct
8 Correct 20 ms 37880 KB Output is correct
9 Correct 180 ms 81116 KB Output is correct
10 Correct 37 ms 45028 KB Output is correct
11 Correct 91 ms 62564 KB Output is correct
12 Correct 39 ms 47056 KB Output is correct
13 Correct 33 ms 42712 KB Output is correct
14 Correct 20 ms 37928 KB Output is correct
15 Correct 19 ms 37972 KB Output is correct
16 Correct 181 ms 81148 KB Output is correct
17 Correct 20 ms 40908 KB Output is correct
18 Correct 20 ms 40952 KB Output is correct
19 Correct 18 ms 37844 KB Output is correct
20 Correct 487 ms 149832 KB Output is correct
21 Correct 501 ms 138404 KB Output is correct
22 Correct 484 ms 149428 KB Output is correct
23 Correct 265 ms 107000 KB Output is correct
24 Correct 74 ms 45072 KB Output is correct
25 Correct 76 ms 45200 KB Output is correct
26 Correct 78 ms 45012 KB Output is correct
27 Correct 327 ms 101324 KB Output is correct
28 Correct 325 ms 101308 KB Output is correct
29 Correct 488 ms 101228 KB Output is correct
30 Correct 462 ms 101276 KB Output is correct
31 Correct 25 ms 40916 KB Output is correct
32 Correct 53 ms 47292 KB Output is correct
33 Correct 55 ms 41848 KB Output is correct
34 Correct 370 ms 149872 KB Output is correct
35 Correct 23 ms 38356 KB Output is correct
36 Correct 39 ms 40048 KB Output is correct
37 Correct 53 ms 42000 KB Output is correct
38 Correct 215 ms 74048 KB Output is correct
39 Correct 265 ms 86324 KB Output is correct
40 Correct 338 ms 98596 KB Output is correct
41 Correct 431 ms 110936 KB Output is correct
42 Correct 476 ms 123448 KB Output is correct
43 Correct 19 ms 41044 KB Output is correct
44 Correct 22 ms 40964 KB Output is correct
45 Correct 23 ms 40948 KB Output is correct
46 Correct 21 ms 37792 KB Output is correct
47 Correct 22 ms 37840 KB Output is correct
48 Correct 21 ms 40932 KB Output is correct
49 Correct 20 ms 40916 KB Output is correct
50 Correct 19 ms 40964 KB Output is correct
51 Correct 22 ms 40952 KB Output is correct
52 Correct 20 ms 37868 KB Output is correct
53 Correct 20 ms 40952 KB Output is correct
54 Correct 23 ms 38012 KB Output is correct
55 Correct 20 ms 37976 KB Output is correct
56 Correct 190 ms 87528 KB Output is correct
57 Correct 361 ms 108508 KB Output is correct
58 Correct 310 ms 108480 KB Output is correct
59 Correct 17 ms 37812 KB Output is correct
60 Correct 22 ms 40940 KB Output is correct
61 Correct 19 ms 37844 KB Output is correct
62 Correct 340 ms 122960 KB Output is correct
63 Correct 292 ms 112120 KB Output is correct
64 Correct 294 ms 117248 KB Output is correct
65 Correct 22 ms 38100 KB Output is correct
66 Correct 21 ms 38248 KB Output is correct
67 Correct 216 ms 85916 KB Output is correct
68 Correct 338 ms 108568 KB Output is correct
69 Correct 453 ms 131012 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 40940 KB Output is correct
2 Correct 19 ms 40956 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 21 ms 40916 KB Output is correct
5 Correct 22 ms 41024 KB Output is correct
6 Correct 23 ms 37792 KB Output is correct
7 Correct 19 ms 37844 KB Output is correct
8 Correct 20 ms 37880 KB Output is correct
9 Correct 180 ms 81116 KB Output is correct
10 Correct 37 ms 45028 KB Output is correct
11 Correct 91 ms 62564 KB Output is correct
12 Correct 39 ms 47056 KB Output is correct
13 Correct 33 ms 42712 KB Output is correct
14 Correct 20 ms 37928 KB Output is correct
15 Correct 19 ms 37972 KB Output is correct
16 Correct 181 ms 81148 KB Output is correct
17 Correct 354 ms 122316 KB Output is correct
18 Correct 317 ms 118652 KB Output is correct
19 Correct 478 ms 149392 KB Output is correct
20 Correct 522 ms 130340 KB Output is correct
21 Correct 411 ms 109240 KB Output is correct
22 Correct 20 ms 41044 KB Output is correct
23 Correct 83 ms 54240 KB Output is correct
24 Correct 31 ms 39292 KB Output is correct
25 Correct 56 ms 41372 KB Output is correct
26 Correct 71 ms 43416 KB Output is correct
27 Correct 251 ms 85504 KB Output is correct
28 Correct 332 ms 96884 KB Output is correct
29 Correct 364 ms 108180 KB Output is correct
30 Correct 440 ms 118912 KB Output is correct
31 Correct 484 ms 130416 KB Output is correct
32 Correct 454 ms 133616 KB Output is correct
33 Correct 310 ms 123036 KB Output is correct
34 Correct 22 ms 38172 KB Output is correct
35 Correct 25 ms 38276 KB Output is correct
36 Correct 233 ms 86828 KB Output is correct
37 Correct 358 ms 110028 KB Output is correct
38 Correct 426 ms 132944 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 40940 KB Output is correct
2 Correct 19 ms 40956 KB Output is correct
3 Correct 19 ms 37844 KB Output is correct
4 Correct 21 ms 40916 KB Output is correct
5 Correct 22 ms 41024 KB Output is correct
6 Correct 23 ms 37792 KB Output is correct
7 Correct 19 ms 37844 KB Output is correct
8 Correct 20 ms 37880 KB Output is correct
9 Correct 180 ms 81116 KB Output is correct
10 Correct 37 ms 45028 KB Output is correct
11 Correct 91 ms 62564 KB Output is correct
12 Correct 39 ms 47056 KB Output is correct
13 Correct 33 ms 42712 KB Output is correct
14 Correct 20 ms 37928 KB Output is correct
15 Correct 19 ms 37972 KB Output is correct
16 Correct 181 ms 81148 KB Output is correct
17 Correct 22 ms 40916 KB Output is correct
18 Correct 19 ms 41044 KB Output is correct
19 Correct 19 ms 40952 KB Output is correct
20 Correct 21 ms 41016 KB Output is correct
21 Correct 21 ms 37880 KB Output is correct
22 Correct 19 ms 40948 KB Output is correct
23 Correct 426 ms 141740 KB Output is correct
24 Correct 21 ms 40952 KB Output is correct
25 Correct 22 ms 41548 KB Output is correct
26 Correct 22 ms 38056 KB Output is correct
27 Correct 25 ms 37992 KB Output is correct
28 Correct 194 ms 81140 KB Output is correct
29 Correct 257 ms 101440 KB Output is correct
30 Correct 340 ms 121620 KB Output is correct
31 Correct 426 ms 141800 KB Output is correct
32 Correct 24 ms 41044 KB Output is correct
33 Correct 20 ms 40948 KB Output is correct
34 Correct 20 ms 40936 KB Output is correct
35 Correct 20 ms 37840 KB Output is correct
36 Correct 19 ms 37804 KB Output is correct
37 Correct 20 ms 40916 KB Output is correct
38 Correct 22 ms 40976 KB Output is correct
39 Correct 25 ms 40916 KB Output is correct
40 Correct 24 ms 40924 KB Output is correct
41 Correct 21 ms 37844 KB Output is correct
42 Correct 22 ms 40980 KB Output is correct
43 Correct 19 ms 37988 KB Output is correct
44 Correct 19 ms 37972 KB Output is correct
45 Correct 199 ms 87428 KB Output is correct
46 Correct 294 ms 108428 KB Output is correct
47 Correct 298 ms 108408 KB Output is correct
48 Correct 20 ms 41044 KB Output is correct
49 Correct 23 ms 41044 KB Output is correct
50 Correct 20 ms 40948 KB Output is correct
51 Correct 23 ms 40952 KB Output is correct
52 Correct 20 ms 41044 KB Output is correct
53 Correct 23 ms 40944 KB Output is correct
54 Correct 22 ms 40940 KB Output is correct
55 Correct 491 ms 143844 KB Output is correct
56 Correct 23 ms 40908 KB Output is correct
57 Correct 26 ms 41932 KB Output is correct
58 Correct 38 ms 44016 KB Output is correct
59 Correct 23 ms 38400 KB Output is correct
60 Correct 230 ms 92264 KB Output is correct
61 Correct 317 ms 110236 KB Output is correct
62 Correct 395 ms 125996 KB Output is correct
63 Correct 473 ms 143940 KB Output is correct
64 Correct 20 ms 37844 KB Output is correct
65 Correct 20 ms 40932 KB Output is correct
66 Correct 20 ms 37896 KB Output is correct
67 Correct 320 ms 123036 KB Output is correct
68 Correct 308 ms 112096 KB Output is correct
69 Correct 306 ms 117256 KB Output is correct
70 Correct 21 ms 38100 KB Output is correct
71 Correct 24 ms 38276 KB Output is correct
72 Correct 249 ms 85708 KB Output is correct
73 Correct 338 ms 108532 KB Output is correct
74 Correct 469 ms 131008 KB Output is correct
75 Correct 446 ms 133580 KB Output is correct
76 Correct 348 ms 123000 KB Output is correct
77 Correct 21 ms 38228 KB Output is correct
78 Correct 27 ms 38352 KB Output is correct
79 Correct 232 ms 86800 KB Output is correct
80 Correct 348 ms 109936 KB Output is correct
81 Correct 454 ms 132944 KB Output is correct
82 Correct 20 ms 40908 KB Output is correct
83 Correct 20 ms 40952 KB Output is correct
84 Correct 18 ms 37844 KB Output is correct
85 Correct 487 ms 149832 KB Output is correct
86 Correct 501 ms 138404 KB Output is correct
87 Correct 484 ms 149428 KB Output is correct
88 Correct 265 ms 107000 KB Output is correct
89 Correct 74 ms 45072 KB Output is correct
90 Correct 76 ms 45200 KB Output is correct
91 Correct 78 ms 45012 KB Output is correct
92 Correct 327 ms 101324 KB Output is correct
93 Correct 325 ms 101308 KB Output is correct
94 Correct 488 ms 101228 KB Output is correct
95 Correct 462 ms 101276 KB Output is correct
96 Correct 25 ms 40916 KB Output is correct
97 Correct 53 ms 47292 KB Output is correct
98 Correct 55 ms 41848 KB Output is correct
99 Correct 370 ms 149872 KB Output is correct
100 Correct 23 ms 38356 KB Output is correct
101 Correct 39 ms 40048 KB Output is correct
102 Correct 53 ms 42000 KB Output is correct
103 Correct 215 ms 74048 KB Output is correct
104 Correct 265 ms 86324 KB Output is correct
105 Correct 338 ms 98596 KB Output is correct
106 Correct 431 ms 110936 KB Output is correct
107 Correct 476 ms 123448 KB Output is correct
108 Correct 19 ms 41044 KB Output is correct
109 Correct 22 ms 40964 KB Output is correct
110 Correct 23 ms 40948 KB Output is correct
111 Correct 21 ms 37792 KB Output is correct
112 Correct 22 ms 37840 KB Output is correct
113 Correct 21 ms 40932 KB Output is correct
114 Correct 20 ms 40916 KB Output is correct
115 Correct 19 ms 40964 KB Output is correct
116 Correct 22 ms 40952 KB Output is correct
117 Correct 20 ms 37868 KB Output is correct
118 Correct 20 ms 40952 KB Output is correct
119 Correct 23 ms 38012 KB Output is correct
120 Correct 20 ms 37976 KB Output is correct
121 Correct 190 ms 87528 KB Output is correct
122 Correct 361 ms 108508 KB Output is correct
123 Correct 310 ms 108480 KB Output is correct
124 Correct 17 ms 37812 KB Output is correct
125 Correct 22 ms 40940 KB Output is correct
126 Correct 19 ms 37844 KB Output is correct
127 Correct 340 ms 122960 KB Output is correct
128 Correct 292 ms 112120 KB Output is correct
129 Correct 294 ms 117248 KB Output is correct
130 Correct 22 ms 38100 KB Output is correct
131 Correct 21 ms 38248 KB Output is correct
132 Correct 216 ms 85916 KB Output is correct
133 Correct 338 ms 108568 KB Output is correct
134 Correct 453 ms 131012 KB Output is correct
135 Correct 354 ms 122316 KB Output is correct
136 Correct 317 ms 118652 KB Output is correct
137 Correct 478 ms 149392 KB Output is correct
138 Correct 522 ms 130340 KB Output is correct
139 Correct 411 ms 109240 KB Output is correct
140 Correct 20 ms 41044 KB Output is correct
141 Correct 83 ms 54240 KB Output is correct
142 Correct 31 ms 39292 KB Output is correct
143 Correct 56 ms 41372 KB Output is correct
144 Correct 71 ms 43416 KB Output is correct
145 Correct 251 ms 85504 KB Output is correct
146 Correct 332 ms 96884 KB Output is correct
147 Correct 364 ms 108180 KB Output is correct
148 Correct 440 ms 118912 KB Output is correct
149 Correct 484 ms 130416 KB Output is correct
150 Correct 454 ms 133616 KB Output is correct
151 Correct 310 ms 123036 KB Output is correct
152 Correct 22 ms 38172 KB Output is correct
153 Correct 25 ms 38276 KB Output is correct
154 Correct 233 ms 86828 KB Output is correct
155 Correct 358 ms 110028 KB Output is correct
156 Correct 426 ms 132944 KB Output is correct
157 Correct 21 ms 40952 KB Output is correct
158 Correct 22 ms 37812 KB Output is correct
159 Correct 19 ms 41020 KB Output is correct
160 Correct 21 ms 40952 KB Output is correct
161 Correct 503 ms 148640 KB Output is correct
162 Correct 394 ms 149824 KB Output is correct
163 Correct 402 ms 138188 KB Output is correct
164 Correct 441 ms 138136 KB Output is correct
165 Correct 512 ms 145416 KB Output is correct
166 Correct 499 ms 147744 KB Output is correct
167 Incorrect 107 ms 58428 KB Solution announced impossible, but it is possible.
168 Halted 0 ms 0 KB -