Submission #774362

#	Time	Username	Problem	Language	Result	Execution time	Memory
774362		LittleCube	Mars (APIO22_mars)	C++17	100 / 100	803 ms	4764 KiB

mars

#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 (stderr)

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 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11