oj.uz

Submission #588507

# Submission time Handle Problem Language Result Execution time Memory
588507 2022-07-03T12:20:56 Z Joshc Mars (APIO22_mars) C++17
100 / 100
 1326 ms 4808 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
 
#define pii pair<int, int>
#define mp make_pair
#define f first
#define s second
 
const int OFFSET = 1e6;
 
/*
00 = nothing
01 = left bracket
10 = rightbracket
11 = underscore
*/
 
string tobracket(int n, vector<vector<int>> comp) {
	// Given a list of components, generate the bracket sequence
	string res(100, '0');
	for (vector<int>& v : comp) {
		if (v.size() == 1) continue;
		res[2*v[0]+1] = '1';
		res[2*v.back()] = '1';
		for (int i=1; i+1<v.size(); i++) res[2*v[i]] = res[2*v[i]+1] = '1'; 
	}
	return res;
}
 
vector<vector<int>> tocomp(int n, string s) {
	// Given a bracket sequence, return the list of components
	vector<vector<int>> res, stack;
	for (int i=0; i<n; i++) {
		if (s[i*2] == '0' && s[i*2+1] == '0') res.push_back({i});
		else if (s[i*2] == '0' && s[i*2+1] == '1') stack.push_back({i});
		else if (s[i*2] == '1' && s[i*2+1] == '0') {
			stack.back().push_back(i);
			res.push_back(stack.back());
			stack.pop_back();
		} else stack.back().push_back(i);
	}
	return res;
}
 
vector<int> getblocks(string frontier) {
	// split the current frontier into blocks
	vector<int> res(frontier.size(), -1);
	int cur = -1;
	for (int i=0; i<frontier.size(); i++) {
		if (frontier[i] == '1') {
			if (!i || frontier[i-1] == '0') cur++;
			res[i] = cur;
		}
	}
	return res;
}
 
struct dsu {
	unordered_map<int, int> parent, sz;
	int comps = 0;
 
	int root(int x) {
		if (parent.find(x) == parent.end()) {
			sz[x] = 1;
			comps++;
			return parent[x] = x;
		}
		return x == parent[x] ? x : parent[x] = root(parent[x]);
	}
 
	void join(int x, int y) {
		x = root(x);
		y = root(y);
		if (x == y) return;
		comps--;
		if (sz[x] > sz[y]) swap(x, y);
		parent[x] = y;
		sz[y] += sz[x];
	}
 
	vector<vector<int>> getcomps() {
		vector<vector<int>> res;
		unordered_map<int, vector<int>> x;
		for (pii p : parent) x[root(p.f)].push_back(p.f);
		for (auto p : x) res.push_back(p.s);
		return res;
	}
};
 
vector<int> reduce(vector<int> v) {
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end())-v.begin());
	return v;
}
 
string process(vector<vector<string>> a, int i, int j, int k, int n) {
	string res(100, '0');
	if (i%2 == 0 && i && i >= j+1) {
		if (k == 0) {
			res[0] = a[0][0][0];
			res[1] = a[0][1][0];
			res[2] = a[1][0][0];
			res[3] = a[1][1][0];
			res[4] = a[2][0][0];
			res[5] = a[2][1][0];
		} else {
			for (int i=0; i<96; i++) res[i+4] = a[2][0][i];
			res[0] = a[0][0][0];
			res[1] = a[0][1][0];
			res[2] = a[1][0][0];
			res[3] = a[1][1][0];
		}
		return res;
	}
	if (j%2 == 0 && j && j >= i+1) {
		if (k == 0) {
			res[0] = a[0][0][0];
			res[1] = a[1][0][0];
			res[2] = a[0][1][0];
			res[3] = a[1][1][0];
			res[4] = a[0][2][0];
			res[5] = a[1][2][0];
		} else {
			for (int i=0; i<96; i++) res[i+4] = a[0][2][i];
			res[0] = a[0][0][0];
			res[1] = a[1][0][0];
			res[2] = a[0][1][0];
			res[3] = a[1][1][0];
		}
		return res;
	}
	if (i == 2*(n-k-1) && i == j) {
		if (k == 0) {
			string frontier;
			frontier += a[2][0][0];
			frontier += a[1][0][0];
			frontier += a[0][0][0];
			frontier += a[0][1][0];
			frontier += a[0][2][0];
			vector<int> blocks = getblocks(frontier);
			int x = *max_element(blocks.begin(), blocks.end())+1;
			unordered_map<int, int> pos = {{6, 0}, {3, 1}, {0, 2}, {1, 3}, {2, 4}};
			dsu d;
 
			for (int i=0; i<3; i++) {
				for (int j=0; j<3; j++) {
					if (a[i][j][0] == '1') d.root(i*3+j); // make sure node is considered
					if (i != 2 && a[i][j][0] == '1' && a[i+1][j][0] == '1') d.join(i*3+j, (i+1)*3+j);
					if (j != 2 && a[i][j][0] == '1' && a[i][j+1][0] == '1') d.join(i*3+j, i*3+j+1);
				}
			}
 
			vector<vector<int>> comps;
			for (vector<int>& comp : d.getcomps()) {
				vector<int> cur;
				for (int i : comp) {
					if (pos.find(i) != pos.end()) cur.push_back(blocks[pos[i]]);
				}
				if (cur.empty()) continue;
				comps.push_back(reduce(cur));
			}
 
			if (n == 1) {
				for (int i=0; i<10; i++) {
					if (d.comps&(1<<i)) res[i] = '1';
				}
				return res;
			}
 
			res = tobracket(x, comps);
			for (int i=0; i<10; i++) {
				if (d.comps&(1<<i)) res[i+90] = '1';
			}
			return res;
		}
 
 
		// for convenience, let's just fill in the entire bottom right square
		int sz = 2*n+1-i;
 
		vector<string> grid(sz, string(sz, '0'));
		grid[0][0] = a[0][0][0];
		grid[0][1] = a[0][1][0];
		grid[1][0] = a[1][0][0];
		grid[1][1] = a[1][1][0];
 
		for (int i=0; i<sz-2; i++) {
			grid[i+2][0] = a[2][0][i*2];
			grid[i+2][1] = a[2][0][i*2+1];
			grid[i+2][2] = a[2][1][i*2+1];
			grid[0][i+2] = a[0][2][i*2];
			grid[1][i+2] = a[0][2][i*2+1];
			grid[2][i+2] = a[1][2][i*2+1];
		}

		dsu d;
		vector<int> order;
		
		for (int i=2; i<sz; i++) {
			if (grid[i][2] == '1') d.root(i*100+2);
			if (grid[2][i] == '1') d.root(200+i);
		}
 
		string inner; // store the inner frontier
		for (int i=sz-1; i>1; i--) {
			inner += grid[i][2];
			order.push_back(i*100+2);
		}
		for (int i=3; i<sz; i++) {
			inner += grid[2][i];
			order.push_back(200+i);
		}
 
		for (int i=1; i<inner.size(); i++) {
			if (inner[i-1] == '1' && inner[i] == '1') d.join(order[i-1], order[i]);
		}
		
		vector<int> innerblocks = getblocks(inner);
		unordered_map<int, int> m;
		for (int i=0; i<innerblocks.size(); i++) m[innerblocks[i]] = order[i];

		int x = *max_element(innerblocks.begin(), innerblocks.end())+1;
		vector<vector<int>> innercomps = tocomp(x, a[2][2]);
		for (vector<int>& comp : innercomps) {
			for (int i : comp) d.join(m[comp[0]], m[i]);
		}
		
		d.comps = 0;
		for (int i=0; i<10; i++) {
			if (a[2][2][90+i] == '1') d.comps |= 1<<i;
		}
 
		for (int i=0; i<sz; i++) {
			for (int j=0; j<sz; j++) {
				if (grid[i][j] == '1') d.root(i*100+j);
			}
		}
 
		for (int i=0; i<sz; i++) {
			for (int j=0; j<sz; j++) {
				if (i+1 != sz && grid[i][j] == '1' && grid[i+1][j] == '1') d.join(i*100+j, (i+1)*100+j);
				if (j+1 != sz && grid[i][j] == '1' && grid[i][j+1] == '1') d.join(i*100+j, i*100+j+1);
			}
		}
		
		order.clear();
		string outer;
		unordered_map<int, int> pos;
		for (int i=sz-1; i>=0; i--) {
			pos[i*100] = outer.size();
			outer += grid[i][0];
		}
		for (int i=1; i<sz; i++) {
			pos[i] = outer.size();
			outer += grid[0][i];
		}
 
		vector<int> blocks = getblocks(outer);
 
		vector<vector<int>> comps;
		for (vector<int>& comp : d.getcomps()) {
			vector<int> cur;
			for (int i : comp) {
				if (pos.find(i) != pos.end()) cur.push_back(blocks[pos[i]]);
			}
			if (cur.empty()) continue;
			comps.push_back(reduce(cur));
		}
 
		if (k == n-1) {
			for (int i=0; i<10; i++) {
				if (d.comps&(1<<i)) res[i] = '1';
			}
			return res;
		}
		res = tobracket(x, comps);
		for (int i=0; i<10; i++) {
			if (d.comps&(1<<i)) res[i+90] = '1';
		}
		return res;
 
	}
	return a[0][0];
}

Compilation message

mars.cpp: In function 'std::string tobracket(int, std::vector<std::vector<int> >)':
mars.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   for (int i=1; i+1<v.size(); i++) res[2*v[i]] = res[2*v[i]+1] = '1';
      |                 ~~~^~~~~~~~~
mars.cpp: In function 'std::vector<int> getblocks(std::string)':
mars.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i=0; i<frontier.size(); i++) {
      |                ~^~~~~~~~~~~~~~~~
mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:215:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  215 |   for (int i=1; i<inner.size(); i++) {
      |                 ~^~~~~~~~~~~~~
mars.cpp:221:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  221 |   for (int i=0; i<innerblocks.size(); i++) m[innerblocks[i]] = order[i];
      |                 ~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct
29 Correct 122 ms 2856 KB Output is correct
30 Correct 176 ms 2992 KB Output is correct
31 Correct 163 ms 2912 KB Output is correct
32 Correct 173 ms 2836 KB Output is correct
33 Correct 163 ms 2868 KB Output is correct
34 Correct 175 ms 2852 KB Output is correct
35 Correct 170 ms 2888 KB Output is correct
36 Correct 166 ms 2972 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct
29 Correct 122 ms 2856 KB Output is correct
30 Correct 176 ms 2992 KB Output is correct
31 Correct 163 ms 2912 KB Output is correct
32 Correct 173 ms 2836 KB Output is correct
33 Correct 163 ms 2868 KB Output is correct
34 Correct 175 ms 2852 KB Output is correct
35 Correct 170 ms 2888 KB Output is correct
36 Correct 166 ms 2972 KB Output is correct
37 Correct 219 ms 3284 KB Output is correct
38 Correct 269 ms 3216 KB Output is correct
39 Correct 287 ms 3208 KB Output is correct
40 Correct 277 ms 3296 KB Output is correct
41 Correct 285 ms 3328 KB Output is correct
42 Correct 285 ms 3344 KB Output is correct
43 Correct 283 ms 3276 KB Output is correct
44 Correct 281 ms 3176 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct
29 Correct 122 ms 2856 KB Output is correct
30 Correct 176 ms 2992 KB Output is correct
31 Correct 163 ms 2912 KB Output is correct
32 Correct 173 ms 2836 KB Output is correct
33 Correct 163 ms 2868 KB Output is correct
34 Correct 175 ms 2852 KB Output is correct
35 Correct 170 ms 2888 KB Output is correct
36 Correct 166 ms 2972 KB Output is correct
37 Correct 219 ms 3284 KB Output is correct
38 Correct 269 ms 3216 KB Output is correct
39 Correct 287 ms 3208 KB Output is correct
40 Correct 277 ms 3296 KB Output is correct
41 Correct 285 ms 3328 KB Output is correct
42 Correct 285 ms 3344 KB Output is correct
43 Correct 283 ms 3276 KB Output is correct
44 Correct 281 ms 3176 KB Output is correct
45 Correct 373 ms 3428 KB Output is correct
46 Correct 437 ms 3480 KB Output is correct
47 Correct 453 ms 3516 KB Output is correct
48 Correct 448 ms 3488 KB Output is correct
49 Correct 424 ms 3452 KB Output is correct
50 Correct 452 ms 3372 KB Output is correct
51 Correct 439 ms 3332 KB Output is correct
52 Correct 430 ms 3400 KB Output is correct
53 Correct 462 ms 3424 KB Output is correct
54 Correct 448 ms 3392 KB Output is correct
55 Correct 445 ms 3364 KB Output is correct
56 Correct 446 ms 3532 KB Output is correct

Subtask #8
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct
29 Correct 122 ms 2856 KB Output is correct
30 Correct 176 ms 2992 KB Output is correct
31 Correct 163 ms 2912 KB Output is correct
32 Correct 173 ms 2836 KB Output is correct
33 Correct 163 ms 2868 KB Output is correct
34 Correct 175 ms 2852 KB Output is correct
35 Correct 170 ms 2888 KB Output is correct
36 Correct 166 ms 2972 KB Output is correct
37 Correct 219 ms 3284 KB Output is correct
38 Correct 269 ms 3216 KB Output is correct
39 Correct 287 ms 3208 KB Output is correct
40 Correct 277 ms 3296 KB Output is correct
41 Correct 285 ms 3328 KB Output is correct
42 Correct 285 ms 3344 KB Output is correct
43 Correct 283 ms 3276 KB Output is correct
44 Correct 281 ms 3176 KB Output is correct
45 Correct 373 ms 3428 KB Output is correct
46 Correct 437 ms 3480 KB Output is correct
47 Correct 453 ms 3516 KB Output is correct
48 Correct 448 ms 3488 KB Output is correct
49 Correct 424 ms 3452 KB Output is correct
50 Correct 452 ms 3372 KB Output is correct
51 Correct 439 ms 3332 KB Output is correct
52 Correct 430 ms 3400 KB Output is correct
53 Correct 462 ms 3424 KB Output is correct
54 Correct 448 ms 3392 KB Output is correct
55 Correct 445 ms 3364 KB Output is correct
56 Correct 446 ms 3532 KB Output is correct
57 Correct 553 ms 3824 KB Output is correct
58 Correct 663 ms 4032 KB Output is correct
59 Correct 658 ms 4104 KB Output is correct
60 Correct 652 ms 4104 KB Output is correct
61 Correct 656 ms 4092 KB Output is correct
62 Correct 648 ms 3992 KB Output is correct
63 Correct 681 ms 4160 KB Output is correct
64 Correct 715 ms 4120 KB Output is correct
65 Correct 668 ms 3960 KB Output is correct
66 Correct 670 ms 3896 KB Output is correct
67 Correct 660 ms 4020 KB Output is correct
68 Correct 646 ms 4164 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct
29 Correct 122 ms 2856 KB Output is correct
30 Correct 176 ms 2992 KB Output is correct
31 Correct 163 ms 2912 KB Output is correct
32 Correct 173 ms 2836 KB Output is correct
33 Correct 163 ms 2868 KB Output is correct
34 Correct 175 ms 2852 KB Output is correct
35 Correct 170 ms 2888 KB Output is correct
36 Correct 166 ms 2972 KB Output is correct
37 Correct 219 ms 3284 KB Output is correct
38 Correct 269 ms 3216 KB Output is correct
39 Correct 287 ms 3208 KB Output is correct
40 Correct 277 ms 3296 KB Output is correct
41 Correct 285 ms 3328 KB Output is correct
42 Correct 285 ms 3344 KB Output is correct
43 Correct 283 ms 3276 KB Output is correct
44 Correct 281 ms 3176 KB Output is correct
45 Correct 373 ms 3428 KB Output is correct
46 Correct 437 ms 3480 KB Output is correct
47 Correct 453 ms 3516 KB Output is correct
48 Correct 448 ms 3488 KB Output is correct
49 Correct 424 ms 3452 KB Output is correct
50 Correct 452 ms 3372 KB Output is correct
51 Correct 439 ms 3332 KB Output is correct
52 Correct 430 ms 3400 KB Output is correct
53 Correct 462 ms 3424 KB Output is correct
54 Correct 448 ms 3392 KB Output is correct
55 Correct 445 ms 3364 KB Output is correct
56 Correct 446 ms 3532 KB Output is correct
57 Correct 553 ms 3824 KB Output is correct
58 Correct 663 ms 4032 KB Output is correct
59 Correct 658 ms 4104 KB Output is correct
60 Correct 652 ms 4104 KB Output is correct
61 Correct 656 ms 4092 KB Output is correct
62 Correct 648 ms 3992 KB Output is correct
63 Correct 681 ms 4160 KB Output is correct
64 Correct 715 ms 4120 KB Output is correct
65 Correct 668 ms 3960 KB Output is correct
66 Correct 670 ms 3896 KB Output is correct
67 Correct 660 ms 4020 KB Output is correct
68 Correct 646 ms 4164 KB Output is correct
69 Correct 811 ms 4168 KB Output is correct
70 Correct 929 ms 4284 KB Output is correct
71 Correct 944 ms 4276 KB Output is correct
72 Correct 954 ms 4340 KB Output is correct
73 Correct 949 ms 4208 KB Output is correct
74 Correct 934 ms 4332 KB Output is correct
75 Correct 936 ms 4296 KB Output is correct
76 Correct 945 ms 4168 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 8 ms 1964 KB Output is correct
3 Correct 8 ms 2152 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1884 KB Output is correct
6 Correct 7 ms 2060 KB Output is correct
7 Correct 13 ms 2104 KB Output is correct
8 Correct 17 ms 2164 KB Output is correct
9 Correct 16 ms 1880 KB Output is correct
10 Correct 16 ms 2064 KB Output is correct
11 Correct 16 ms 2120 KB Output is correct
12 Correct 15 ms 2128 KB Output is correct
13 Correct 16 ms 2256 KB Output is correct
14 Correct 27 ms 2464 KB Output is correct
15 Correct 41 ms 2524 KB Output is correct
16 Correct 40 ms 2604 KB Output is correct
17 Correct 41 ms 2584 KB Output is correct
18 Correct 43 ms 2520 KB Output is correct
19 Correct 40 ms 2588 KB Output is correct
20 Correct 40 ms 2548 KB Output is correct
21 Correct 59 ms 2508 KB Output is correct
22 Correct 86 ms 2644 KB Output is correct
23 Correct 88 ms 2664 KB Output is correct
24 Correct 92 ms 2680 KB Output is correct
25 Correct 82 ms 2724 KB Output is correct
26 Correct 83 ms 2600 KB Output is correct
27 Correct 93 ms 2748 KB Output is correct
28 Correct 84 ms 2632 KB Output is correct
29 Correct 122 ms 2856 KB Output is correct
30 Correct 176 ms 2992 KB Output is correct
31 Correct 163 ms 2912 KB Output is correct
32 Correct 173 ms 2836 KB Output is correct
33 Correct 163 ms 2868 KB Output is correct
34 Correct 175 ms 2852 KB Output is correct
35 Correct 170 ms 2888 KB Output is correct
36 Correct 166 ms 2972 KB Output is correct
37 Correct 219 ms 3284 KB Output is correct
38 Correct 269 ms 3216 KB Output is correct
39 Correct 287 ms 3208 KB Output is correct
40 Correct 277 ms 3296 KB Output is correct
41 Correct 285 ms 3328 KB Output is correct
42 Correct 285 ms 3344 KB Output is correct
43 Correct 283 ms 3276 KB Output is correct
44 Correct 281 ms 3176 KB Output is correct
45 Correct 373 ms 3428 KB Output is correct
46 Correct 437 ms 3480 KB Output is correct
47 Correct 453 ms 3516 KB Output is correct
48 Correct 448 ms 3488 KB Output is correct
49 Correct 424 ms 3452 KB Output is correct
50 Correct 452 ms 3372 KB Output is correct
51 Correct 439 ms 3332 KB Output is correct
52 Correct 430 ms 3400 KB Output is correct
53 Correct 462 ms 3424 KB Output is correct
54 Correct 448 ms 3392 KB Output is correct
55 Correct 445 ms 3364 KB Output is correct
56 Correct 446 ms 3532 KB Output is correct
57 Correct 553 ms 3824 KB Output is correct
58 Correct 663 ms 4032 KB Output is correct
59 Correct 658 ms 4104 KB Output is correct
60 Correct 652 ms 4104 KB Output is correct
61 Correct 656 ms 4092 KB Output is correct
62 Correct 648 ms 3992 KB Output is correct
63 Correct 681 ms 4160 KB Output is correct
64 Correct 715 ms 4120 KB Output is correct
65 Correct 668 ms 3960 KB Output is correct
66 Correct 670 ms 3896 KB Output is correct
67 Correct 660 ms 4020 KB Output is correct
68 Correct 646 ms 4164 KB Output is correct
69 Correct 811 ms 4168 KB Output is correct
70 Correct 929 ms 4284 KB Output is correct
71 Correct 944 ms 4276 KB Output is correct
72 Correct 954 ms 4340 KB Output is correct
73 Correct 949 ms 4208 KB Output is correct
74 Correct 934 ms 4332 KB Output is correct
75 Correct 936 ms 4296 KB Output is correct
76 Correct 945 ms 4168 KB Output is correct
77 Correct 950 ms 4216 KB Output is correct
78 Correct 1266 ms 4680 KB Output is correct
79 Correct 1287 ms 4644 KB Output is correct
80 Correct 1299 ms 4524 KB Output is correct
81 Correct 1311 ms 4584 KB Output is correct
82 Correct 1313 ms 4668 KB Output is correct
83 Correct 1326 ms 4484 KB Output is correct
84 Correct 1303 ms 4808 KB Output is correct