oj.uz

Submission #774362

# Submission time Handle Problem Language Result Execution time Memory
774362 2023-07-05T15:51:55 Z LittleCube Mars (APIO22_mars) C++17
100 / 100
 803 ms 4764 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include "mars.h"
#ifndef EVAL
#include "mars_grader.cpp"
#endif
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

int get_count(string s)
{
	int ans = 0;
	for (int i = 92; i <= 99; i++)
		ans = ans * 2 + (s[i] == '1');
	return ans;
}

struct DSU
{
	int dsu[400];
	void init(int n)
	{
		for (int i = 0; i <= n + 5; i++)
			dsu[i] = i;
	}
	int find(int k)
	{
		return dsu[k] == k ? k : dsu[k] = find(dsu[k]);
	}
	int merge(int u, int v)
	{
		u = find(u), v = find(v);
		if (u == v)
			return 0;
		dsu[u] = v;
		return 1;
	}
} dsu;

string FtoB(string f)
{
	// cerr << f << " to ";
	while (f.size() % 3)
		f.push_back('0');
	string b;
	for (int i = 0; i < f.size(); i += 3)
	{
		bitset<7> ch = (f[i] - '0') + 5 * (f[i + 1] - '0') + 25 * (f[i + 2] - '0');
		string s = ch.to_string();
		reverse(s.begin(), s.end());
		b += s;
	}
	// cerr << b << '\n';
	return b;
}

string BtoF(string b, int sz)
{
	string f;
	// cerr << b << " to ";
	for (int i = 0; i < b.size(); i += 7)
	{
		string sub = b.substr(i, 7);
		reverse(sub.begin(), sub.end());
		bitset<7> ch(sub);
		int s = ch.to_ulong();
		f += (char)('0' + s % 5);
		f += (char)('0' + s / 5 % 5);
		f += (char)('0' + s / 25 % 5);
	}
	f.resize(sz);
	// cerr << f << '\n';
	return f;
}

vector<int> parse_corner(int n, int &idx, string s)
{
	vector<int> res(2 * n - 1, 0), mono;
	// cerr << "parse " << s << '\n';
	s.resize(91);
	string t = BtoF(s, 2 * n - 1);
	for (int i = 0; i < 2 * n - 1; i++)
	{
		if (t[i] == '0')
			res[i] = 0;
		else if (t[i] == '1')
			res[i] = ++idx;
		else if (t[i] == '2')
		{
			mono.emplace_back(++idx);
			res[i] = mono.back();
		}
		else if (t[i] == '3')
		{
			res[i] = mono.back();
			mono.pop_back();
		}
		else
			res[i] = mono.back();
		
	}
	// for (auto i : res)
	// 	cerr << i << ' ';
	// cerr << '\n';
	return res;
}

vector<int> parse_edge(int n, int &idx, string s)
{
	// cerr << "parsE " << s << '\n';
	vector<int> res(n, 0);
	for (int i = 0, j = 0; i < n; i++, j++)
	{
		if (s[j] == '0')
			res[i] = 0;
		else
		{
			if (i && s[j - 1] == '1')
				res[i] = res[i - 1];
			else
				res[i] = ++idx;
		}
	}
	// for (auto i : res)
	// 	cerr << i << ' ';
	// cerr << '\n';
	return res;
}

// for corner:
// new: 10, end: 01, continue: 11, zero: 00
// for edge:
// has: 1, no: 0, last 10 bits: count
// first 66 bits: record side, last 10 bits: count
// only border cells in charge, others record themselves

string merge_edge(int n, bool add, string edge)
{
	int tot = get_count(edge) + (edge[0] == '0' && add);

	string ans = string(100, '0');

	for (int i = n; i >= 1; i--)
		ans[i] = edge[i - 1];
	ans[0] = (add ? '1' : '0');

	for (int i = 99; i >= 92; i--)
	{
		if (tot % 2)
			ans[i] = '1';
		tot /= 2;
	}
	return ans;
}

string merge_corner(int n, string before, string corner, string after, string middle)
{
	int idx = 0, tot = get_count(before) + get_count(corner) + get_count(after) + get_count(middle);

	dsu.init(4 * n);

	vector<int> cor = parse_corner(n, idx, corner),
				bef = parse_edge(n, idx, before),
				aft = parse_edge(n, idx, after),
				res(2 * n + 1, 0);

	int mid = (middle[0] == '1' ? ++idx : 0);
	reverse(bef.begin(), bef.end());
	for (int i = 0; i < n; i++)
		if (cor[i] && bef[i])
			tot -= dsu.merge(cor[i], bef[i]);
	for (int i = 0; i < n; i++)
		if (cor[i + n - 1] && aft[i])
			tot -= dsu.merge(cor[i + n - 1], aft[i]);
	if (bef[n - 1] && mid)
		tot -= dsu.merge(bef[n - 1], mid);
	if (aft[0] && mid)
		tot -= dsu.merge(aft[0], mid);
	for (int i = 0; i < n; i++)
		res[i] = dsu.find(bef[i]);
	res[n] = dsu.find(mid);
	for (int i = 0; i < n; i++)
		res[n + 1 + i] = dsu.find(aft[i]);

	vector<int> mono, vis(4 * n + 5, 0), single(4 * n + 5, 0), last(4 * n + 5, 0);

	for (int i = 0; i < 2 * n + 1; i++)
		single[res[i]]++, last[res[i]] = i;
	
	string t;
	for (int i = 0; i < 2 * n + 1; i++)
	{
		if (res[i] == 0)
			t += "0";
		else
		{
			if (vis[res[i]] == 0)
			{
				vis[res[i]] = 1;
				if (single[res[i]] == 1)
					t += "1";
				else
				{
					mono.emplace_back(res[i]);
					t += "2";
				}
			}
			else
			{
				if (i == last[res[i]])
				{
					mono.pop_back();
					t += "3";
				}
				else
					t += "4";
			}
		}
	}

	string ans = FtoB(t);
	if (n == 19)
		cerr << ans.size() << '\n';
	ans.resize(100, '0');
	for (int i = 99; i >= 92; i--)
	{
		// assert(ans[i] == '0');
		if (tot % 2)
			ans[i] = '1';
		tot /= 2;
	}

	return ans;
}

string process(vector<vector<string>> a, int i, int j, int k, int n)
{
	k++;
	i += k, j += k;
	if (k == 1)
		for (int x = 0; x < 3; x++)
			for (int y = 0; y < 3; y++)
				if (a[x][y][0] == '1')
					a[x][y][99] = '1';
			
	
	// return answer
	if (k == n)
	{
		int idx = 0, tot = 0;
		for (int x = 0; x < 3; x++)
			for (int y = 0; y < 3; y++)
				tot += get_count(a[x][y]);
		// cerr << tot << '\n';
		dsu.init(9 * n + 5);

		vector<int> ul = parse_corner(n, idx, a[0][0]),
					ur = parse_corner(n, idx, a[0][2]),
					dr = parse_corner(n, idx, a[2][2]),
					dl = parse_corner(n, idx, a[2][0]),
					l = parse_edge(n, idx, a[1][0]),
					r = parse_edge(n, idx, a[1][2]),
					u = parse_edge(n, idx, a[0][1]),
					d = parse_edge(n, idx, a[2][1]);
		int mid = (a[1][1][0] == '1' ? ++idx : 0);

#define merge1(a, b)            \
	for (int p = 0; p < n; p++) \
		if (a[p] && b[p])       \
			tot -= dsu.merge(a[p], b[p]);
#define merge2(a, b)              \
	for (int p = 0; p < n; p++)   \
		if (a[p + n - 1] && b[p]) \
			tot -= dsu.merge(a[p + n - 1], b[p]);

		merge2(ul, u);
		merge2(ur, r);
		merge2(dr, d);
		merge2(dl, l);

		if (mid && l[0])
			tot -= dsu.merge(mid, l[0]);
		if (mid && r[0])
			tot -= dsu.merge(mid, r[0]);
		if (mid && d[0])
			tot -= dsu.merge(mid, d[0]);
		if (mid && u[0])
			tot -= dsu.merge(mid, u[0]);

		reverse(l.begin(), l.end());
		reverse(r.begin(), r.end());
		reverse(d.begin(), d.end());
		reverse(u.begin(), u.end());

		merge1(ul, l);
		merge1(ur, u);
		merge1(dr, r);
		merge1(dl, d);

		string ans = string(100, '0');
		for (int p = 0; p < 10; p++)
		{
			if (tot % 2)
				ans[p] = '1';
			tot /= 2;
		}
		return ans;
	}
	int sz = k;
	// top left
	if (i == k && j == k)
		return merge_corner(sz, a[1][0], a[0][0], a[0][1], a[1][1]);
	// top right
	if (i == k && j + k == 2 * n)
		return merge_corner(sz, a[0][1], a[0][2], a[1][2], a[1][1]);
	// bottom left
	if (i + k == 2 * n && j == k)
		return merge_corner(sz, a[2][1], a[2][0], a[1][0], a[1][1]);
	// bottom right
	if (i + k == 2 * n && j + k == 2 * n)
		return merge_corner(sz, a[1][2], a[2][2], a[2][1], a[1][1]);
	// top
	if (i == k)
		return merge_edge(sz, a[1][1][0] == '1', a[0][1]);
	// left
	if (j == k)
		return merge_edge(sz, a[1][1][0] == '1', a[1][0]);
	// bottom
	if (i + k == 2 * n)
		return merge_edge(sz, a[1][1][0] == '1', a[2][1]);
	// right
	if (j + k == 2 * n)
		return merge_edge(sz, a[1][1][0] == '1', a[1][2]);

	return a[1][1];
}

Compilation message

mars.cpp: In function 'std::string FtoB(std::string)':
mars.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = 0; i < f.size(); i += 3)
      |                  ~~^~~~~~~~~~
mars.cpp: In function 'std::string BtoF(std::string, int)':
mars.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i = 0; i < b.size(); i += 7)
      |                  ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2060 KB Output is correct
2 Correct 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 KB Output is correct
29 Correct 69 ms 2800 KB Output is correct
30 Correct 100 ms 2852 KB Output is correct
31 Correct 98 ms 2848 KB Output is correct
32 Correct 98 ms 2852 KB Output is correct
33 Correct 96 ms 2964 KB Output is correct
34 Correct 107 ms 2856 KB Output is correct
35 Correct 93 ms 2892 KB Output is correct
36 Correct 97 ms 2856 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 KB Output is correct
29 Correct 69 ms 2800 KB Output is correct
30 Correct 100 ms 2852 KB Output is correct
31 Correct 98 ms 2848 KB Output is correct
32 Correct 98 ms 2852 KB Output is correct
33 Correct 96 ms 2964 KB Output is correct
34 Correct 107 ms 2856 KB Output is correct
35 Correct 93 ms 2892 KB Output is correct
36 Correct 97 ms 2856 KB Output is correct
37 Correct 138 ms 3128 KB Output is correct
38 Correct 166 ms 3456 KB Output is correct
39 Correct 167 ms 3212 KB Output is correct
40 Correct 172 ms 3392 KB Output is correct
41 Correct 169 ms 3296 KB Output is correct
42 Correct 182 ms 3240 KB Output is correct
43 Correct 180 ms 3376 KB Output is correct
44 Correct 170 ms 3500 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 KB Output is correct
29 Correct 69 ms 2800 KB Output is correct
30 Correct 100 ms 2852 KB Output is correct
31 Correct 98 ms 2848 KB Output is correct
32 Correct 98 ms 2852 KB Output is correct
33 Correct 96 ms 2964 KB Output is correct
34 Correct 107 ms 2856 KB Output is correct
35 Correct 93 ms 2892 KB Output is correct
36 Correct 97 ms 2856 KB Output is correct
37 Correct 138 ms 3128 KB Output is correct
38 Correct 166 ms 3456 KB Output is correct
39 Correct 167 ms 3212 KB Output is correct
40 Correct 172 ms 3392 KB Output is correct
41 Correct 169 ms 3296 KB Output is correct
42 Correct 182 ms 3240 KB Output is correct
43 Correct 180 ms 3376 KB Output is correct
44 Correct 170 ms 3500 KB Output is correct
45 Correct 215 ms 3452 KB Output is correct
46 Correct 264 ms 3352 KB Output is correct
47 Correct 268 ms 3376 KB Output is correct
48 Correct 264 ms 3536 KB Output is correct
49 Correct 275 ms 3480 KB Output is correct
50 Correct 284 ms 3424 KB Output is correct
51 Correct 284 ms 3488 KB Output is correct
52 Correct 275 ms 3380 KB Output is correct
53 Correct 270 ms 3484 KB Output is correct
54 Correct 269 ms 3372 KB Output is correct
55 Correct 277 ms 3396 KB Output is correct
56 Correct 270 ms 3428 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 KB Output is correct
29 Correct 69 ms 2800 KB Output is correct
30 Correct 100 ms 2852 KB Output is correct
31 Correct 98 ms 2848 KB Output is correct
32 Correct 98 ms 2852 KB Output is correct
33 Correct 96 ms 2964 KB Output is correct
34 Correct 107 ms 2856 KB Output is correct
35 Correct 93 ms 2892 KB Output is correct
36 Correct 97 ms 2856 KB Output is correct
37 Correct 138 ms 3128 KB Output is correct
38 Correct 166 ms 3456 KB Output is correct
39 Correct 167 ms 3212 KB Output is correct
40 Correct 172 ms 3392 KB Output is correct
41 Correct 169 ms 3296 KB Output is correct
42 Correct 182 ms 3240 KB Output is correct
43 Correct 180 ms 3376 KB Output is correct
44 Correct 170 ms 3500 KB Output is correct
45 Correct 215 ms 3452 KB Output is correct
46 Correct 264 ms 3352 KB Output is correct
47 Correct 268 ms 3376 KB Output is correct
48 Correct 264 ms 3536 KB Output is correct
49 Correct 275 ms 3480 KB Output is correct
50 Correct 284 ms 3424 KB Output is correct
51 Correct 284 ms 3488 KB Output is correct
52 Correct 275 ms 3380 KB Output is correct
53 Correct 270 ms 3484 KB Output is correct
54 Correct 269 ms 3372 KB Output is correct
55 Correct 277 ms 3396 KB Output is correct
56 Correct 270 ms 3428 KB Output is correct
57 Correct 318 ms 3904 KB Output is correct
58 Correct 374 ms 4084 KB Output is correct
59 Correct 378 ms 4120 KB Output is correct
60 Correct 398 ms 4084 KB Output is correct
61 Correct 396 ms 4112 KB Output is correct
62 Correct 403 ms 4000 KB Output is correct
63 Correct 401 ms 4124 KB Output is correct
64 Correct 408 ms 3984 KB Output is correct
65 Correct 391 ms 4376 KB Output is correct
66 Correct 411 ms 4064 KB Output is correct
67 Correct 380 ms 4136 KB Output is correct
68 Correct 400 ms 4160 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 KB Output is correct
29 Correct 69 ms 2800 KB Output is correct
30 Correct 100 ms 2852 KB Output is correct
31 Correct 98 ms 2848 KB Output is correct
32 Correct 98 ms 2852 KB Output is correct
33 Correct 96 ms 2964 KB Output is correct
34 Correct 107 ms 2856 KB Output is correct
35 Correct 93 ms 2892 KB Output is correct
36 Correct 97 ms 2856 KB Output is correct
37 Correct 138 ms 3128 KB Output is correct
38 Correct 166 ms 3456 KB Output is correct
39 Correct 167 ms 3212 KB Output is correct
40 Correct 172 ms 3392 KB Output is correct
41 Correct 169 ms 3296 KB Output is correct
42 Correct 182 ms 3240 KB Output is correct
43 Correct 180 ms 3376 KB Output is correct
44 Correct 170 ms 3500 KB Output is correct
45 Correct 215 ms 3452 KB Output is correct
46 Correct 264 ms 3352 KB Output is correct
47 Correct 268 ms 3376 KB Output is correct
48 Correct 264 ms 3536 KB Output is correct
49 Correct 275 ms 3480 KB Output is correct
50 Correct 284 ms 3424 KB Output is correct
51 Correct 284 ms 3488 KB Output is correct
52 Correct 275 ms 3380 KB Output is correct
53 Correct 270 ms 3484 KB Output is correct
54 Correct 269 ms 3372 KB Output is correct
55 Correct 277 ms 3396 KB Output is correct
56 Correct 270 ms 3428 KB Output is correct
57 Correct 318 ms 3904 KB Output is correct
58 Correct 374 ms 4084 KB Output is correct
59 Correct 378 ms 4120 KB Output is correct
60 Correct 398 ms 4084 KB Output is correct
61 Correct 396 ms 4112 KB Output is correct
62 Correct 403 ms 4000 KB Output is correct
63 Correct 401 ms 4124 KB Output is correct
64 Correct 408 ms 3984 KB Output is correct
65 Correct 391 ms 4376 KB Output is correct
66 Correct 411 ms 4064 KB Output is correct
67 Correct 380 ms 4136 KB Output is correct
68 Correct 400 ms 4160 KB Output is correct
69 Correct 486 ms 4120 KB Output is correct
70 Correct 572 ms 4348 KB Output is correct
71 Correct 559 ms 4420 KB Output is correct
72 Correct 558 ms 4300 KB Output is correct
73 Correct 544 ms 4400 KB Output is correct
74 Correct 544 ms 4300 KB Output is correct
75 Correct 550 ms 4364 KB Output is correct
76 Correct 560 ms 4240 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 6 ms 1876 KB Output is correct
3 Correct 8 ms 1744 KB Output is correct
4 Correct 7 ms 2216 KB Output is correct
5 Correct 8 ms 1740 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 8 ms 1708 KB Output is correct
8 Correct 10 ms 2120 KB Output is correct
9 Correct 8 ms 2068 KB Output is correct
10 Correct 9 ms 1732 KB Output is correct
11 Correct 8 ms 2020 KB Output is correct
12 Correct 8 ms 1856 KB Output is correct
13 Correct 10 ms 2136 KB Output is correct
14 Correct 17 ms 2504 KB Output is correct
15 Correct 24 ms 2704 KB Output is correct
16 Correct 24 ms 2500 KB Output is correct
17 Correct 32 ms 2480 KB Output is correct
18 Correct 26 ms 2624 KB Output is correct
19 Correct 27 ms 2596 KB Output is correct
20 Correct 24 ms 2652 KB Output is correct
21 Correct 41 ms 2708 KB Output is correct
22 Correct 51 ms 2688 KB Output is correct
23 Correct 59 ms 2776 KB Output is correct
24 Correct 51 ms 2716 KB Output is correct
25 Correct 55 ms 2712 KB Output is correct
26 Correct 55 ms 2688 KB Output is correct
27 Correct 51 ms 2800 KB Output is correct
28 Correct 52 ms 2716 KB Output is correct
29 Correct 69 ms 2800 KB Output is correct
30 Correct 100 ms 2852 KB Output is correct
31 Correct 98 ms 2848 KB Output is correct
32 Correct 98 ms 2852 KB Output is correct
33 Correct 96 ms 2964 KB Output is correct
34 Correct 107 ms 2856 KB Output is correct
35 Correct 93 ms 2892 KB Output is correct
36 Correct 97 ms 2856 KB Output is correct
37 Correct 138 ms 3128 KB Output is correct
38 Correct 166 ms 3456 KB Output is correct
39 Correct 167 ms 3212 KB Output is correct
40 Correct 172 ms 3392 KB Output is correct
41 Correct 169 ms 3296 KB Output is correct
42 Correct 182 ms 3240 KB Output is correct
43 Correct 180 ms 3376 KB Output is correct
44 Correct 170 ms 3500 KB Output is correct
45 Correct 215 ms 3452 KB Output is correct
46 Correct 264 ms 3352 KB Output is correct
47 Correct 268 ms 3376 KB Output is correct
48 Correct 264 ms 3536 KB Output is correct
49 Correct 275 ms 3480 KB Output is correct
50 Correct 284 ms 3424 KB Output is correct
51 Correct 284 ms 3488 KB Output is correct
52 Correct 275 ms 3380 KB Output is correct
53 Correct 270 ms 3484 KB Output is correct
54 Correct 269 ms 3372 KB Output is correct
55 Correct 277 ms 3396 KB Output is correct
56 Correct 270 ms 3428 KB Output is correct
57 Correct 318 ms 3904 KB Output is correct
58 Correct 374 ms 4084 KB Output is correct
59 Correct 378 ms 4120 KB Output is correct
60 Correct 398 ms 4084 KB Output is correct
61 Correct 396 ms 4112 KB Output is correct
62 Correct 403 ms 4000 KB Output is correct
63 Correct 401 ms 4124 KB Output is correct
64 Correct 408 ms 3984 KB Output is correct
65 Correct 391 ms 4376 KB Output is correct
66 Correct 411 ms 4064 KB Output is correct
67 Correct 380 ms 4136 KB Output is correct
68 Correct 400 ms 4160 KB Output is correct
69 Correct 486 ms 4120 KB Output is correct
70 Correct 572 ms 4348 KB Output is correct
71 Correct 559 ms 4420 KB Output is correct
72 Correct 558 ms 4300 KB Output is correct
73 Correct 544 ms 4400 KB Output is correct
74 Correct 544 ms 4300 KB Output is correct
75 Correct 550 ms 4364 KB Output is correct
76 Correct 560 ms 4240 KB Output is correct
77 Correct 549 ms 4272 KB Output is correct
78 Correct 765 ms 4764 KB Output is correct
79 Correct 738 ms 4604 KB Output is correct
80 Correct 776 ms 4648 KB Output is correct
81 Correct 727 ms 4760 KB Output is correct
82 Correct 770 ms 4704 KB Output is correct
83 Correct 803 ms 4732 KB Output is correct
84 Correct 752 ms 4704 KB Output is correct