oj.uz

Submission #740956

# Submission time Handle Problem Language Result Execution time Memory
740956 2023-05-13T10:26:24 Z LittleCube Mars (APIO22_mars) C++17
6 / 100
 13 ms 2240 KB 
#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 region[41][41][21];

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

struct DSU
{
	int dsu[200];
	void init(int n)
	{
		for (int i = 0; i <= n; 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;

vector<int> parse_corner(int n, int &idx, string s)
{
	vector<int> res(2 * n - 1, 0), mono;
	for (int i = 0, j = 0; i < 2 * n - 1; i++, j += 2)
	{
		while (s[j] == '0' && s[j + 1] == '1')
		{
			mono.pop_back();
			j += 2;
		}
		if (s[j] == '1' && s[j + 1] == '0')
		{
			mono.emplace_back(++idx);
			res[i] = mono.back();
		}
		if (s[j] == '0' && s[j + 1] == '0')
			res[i] = 0;

		if (s[j] == '1' && s[j + 1] == '1')
			res[i] = mono.back();
	}
	return res;
}

vector<int> parse_edge(int n, int &idx, string s)
{
	vector<int> res(n, 0), mono;
	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;
		}
	}
	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 > 89; 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]);

	string ans = string(100, '0');
	vector<int> mono, vis(4 * n + 1, 0);
	for (int i = 0, j = 0; i < 2 * n + 1; i++, j += 2)
	{
		assert(j + 1 < 89);
		if (res[i] == 0)
			ans[j] = ans[j + 1] = '0';
		else
		{
			if (vis[res[i]] == 0)
			{
				vis[res[i]] = 1;
				mono.emplace_back(res[i]);
				ans[j] = '1', ans[j + 1] = '0';
			}
			else
			{
				while (mono.back() != res[i])
				{
					ans[j] = '0', ans[j + 1] = '1';
					j += 2;
				}
				ans[j] = '1', ans[j + 1] = '1';
			}
		}
	}
	for (int i = 99; i > 89; i--)
	{
		if (tot % 2)
			ans[i] = '1';
		tot /= 2;
	}
	// for (int i : bef)
	// 	cerr << i << ' ';
	// cerr << '\n';
	// for (int i : cor)
	// 	cerr << i << ' ';
	// cerr << '\n';
	// for (int i : aft)
	// 	cerr << i << ' ';
	// cerr << '\n';
	// cerr << mid << ' ';
	// cerr << '\n';
	// cerr << "merge into\n";
	// for (int i : res)
	// 	cerr << i << ' ';
	// cerr << '\n';
	// idx = 0;
	// res = parse_corner(n + 1, idx, ans);
	// cerr << "decode as\n";
	// for (int i : res)
	// 	cerr << i << ' ';
	// cerr << '\n';
	// cerr << '\n';
	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][0] = '1', a[x][y][1] = '0', a[x][y][2] = '0', a[x][y][3] = '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 + 1);

		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];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1876 KB Output is correct
2 Correct 8 ms 2020 KB Output is correct
3 Correct 8 ms 2216 KB Output is correct
4 Correct 8 ms 2240 KB Output is correct
5 Correct 8 ms 1988 KB Output is correct
6 Correct 8 ms 2000 KB Output is correct
7 Correct 13 ms 1968 KB Output is correct
8 Incorrect 2 ms 280 KB Incorrect
9 Halted 0 ms 0 KB -