Submission #789710

#	Time	Username	Problem	Language	Result	Execution time	Memory
789710		GusterGoose27	Mars (APIO22_mars)	C++17	100 / 100	964 ms	6860 KiB

mars

#include "mars.h"

#include <bits/stdc++.h>

using namespace std;

bool val(string &s, int p = 0) {
	return s[p]-'0';
}

int find(int i, vector<int> &uf) {
	return uf[i] == i ? i : uf[i] = find(uf[i], uf);
}

void merge(int a, int b, vector<int> &uf) {
	a = find(a, uf);
	b = find(b, uf);
	if (a != b) uf[a] = b;
}

/*

BIT ALLOCATION:

For main diag, first bit is for value,
	next 44 bits are for start and then end union find when starting from the bottom,
		going up, and then right
	last 10 bits are for the answer

For off diag, first 50 bits represent going down/right,
	and next 50 bits are down/right one row/column over

*/

string process(vector<vector<string>> visible, int i, int j, int k, int n) {
	if (i < 2*(n-k-1) && j < 2*(n-k-1)) return visible[0][0];
	int m = 2*k+3;
	if (i == j) {
		if (i & 1) return visible[0][0];
		bool **grid;
		grid = new bool*[m];
		for (int a = 0; a < m; a++) {
			grid[a] = new bool[m];
			fill(grid[a], grid[a]+m, 0);
		} // make the grid
		for (int a = 0; a < 3; a++) {
			for (int b = 0; b < 3; b++)
				grid[a][b] = val(visible[a][b]);
		}
		for (int b = 3; b < m; b++) {
			grid[b][0] = val(visible[2][0], b-2);
			grid[b][1] = val(visible[2][1], b-2);
			grid[b][2] = val(visible[2][1], 50+b-2);
			grid[0][b] = val(visible[0][2], b-2);
			grid[1][b] = val(visible[1][2], b-2);
			grid[2][b] = val(visible[1][2], 50+b-2);
		}
		// for (int a = 0; a < m; a++) {
		// 	for (int b = 0; b < m; b++) {
		// 		cerr << grid[a][b] << ' ';
		// 	}
		// 	cerr << '\n';
		// }
		// extract current answer from visible[2][2]
		int ans = 0;
		vector<int> uf(m*m);
		iota(uf.begin(), uf.end(), 0);
		if (m > 3) {
			for (int a = 0; a < 10; a++) {
				ans += (val(visible[2][2], 100-a-1)<<a);
			}
			for (int b = 0; b < m-2; b++) {
				for (int a = 0; a < 2; a++) {
					grid[b+2][1+a] = val(visible[2][1], 50*a+b);
					grid[1+a][b+2] = val(visible[1][2], 50*a+b);
				}
				grid[b+2][0] = val(visible[2][0], b);
				grid[0][b+2] = val(visible[0][2], b);
			}
			vector<int> starts;
			int p = 0;
			// cerr << visible[2][2] << '\n';
			bool prv = 0;
			int pid;
			for (int a = m-1; a >= 2; a--) {
				for (int b = 2; b < m; b++) {
					if (a != 2 && b != 2) continue;
					if (!grid[a][b]) {
						prv = 0;
						continue;
					}
					if (prv) {
						merge(m*a+b, pid, uf);
						pid = m*a+b;
						continue;
					}
					prv = 1;
					bool is_start = val(visible[2][2], p+1);
					bool is_end = val(visible[2][2], p+45);
					int cur = m*a+b;
					pid = cur;
					p++;
					if (is_end) {
						// if (starts.empty()) exit(0);
						assert(starts.size());
						merge(starts.back(), cur, uf);
						starts.pop_back();
						// cerr << "0\n";
					}
					if (is_start) {
						starts.push_back(cur);
						// cerr << "1\n";
					}
				}
			}
			assert(starts.empty());
			for (int a = m-1; a >= 2; a--) {
				for (int b = 2; b < m; b++) {
					if (a != 2 && b != 2) continue;
					if (!grid[a][b]) continue;
					int cur = m*a+b;
					ans -= (uf[cur] == cur); // this cc is currently represented
				}
			}
		}
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < m; b++) {
				if (a < m-1 && grid[a][b] && grid[a+1][b]) merge(m*a+b, m*a+b+m, uf);
				if (b < m-1 && grid[a][b] && grid[a][b+1]) merge(m*a+b, m*a+b+1, uf);
			}
		}
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < m; b++) {
				ans += (grid[a][b] && uf[m*a+b] == m*a+b);
			}
		}
		string res(100, '0');
		res[0] = visible[0][0][0];
		if (i == 0) {
			int p = 0;
			while (ans) {
				res[p] = '0'+(ans&1);
				ans /= 2;
				p++;
			}
		}
		else {
			for (int p = 0; p < 10; p++, ans /= 2) res[100-p-1] = '0'+(ans&1);
			vector<char> seen(m*m, 0);
			int p = 0;
			bool prv = 0;
			for (int a = m-1; a >= 0; a--) {
				for (int b = 0; b < m; b++) {
					if (a && b) continue;
					if (!grid[a][b]) {
						prv = 0;
						continue;
					}
					if (prv) continue;
					prv = 1;
					res[45+p] = '0'+seen[find(m*a+b, uf)];
					seen[find(m*a+b, uf)] = 1;
					p++;
				}
			}
			fill(seen.begin(), seen.end(), 0);
			prv = 0;
			for (int b = m-1; b >= 0; b--) {
				for (int a = 0; a < m; a++) {
					if (a && b) continue;
					if (!grid[a][b]) {
						prv = 0;
						continue;
					}
					if (prv) continue;
					prv = 1;
					--p;
					res[1+p] = '0'+seen[find(m*a+b, uf)];
					seen[find(m*a+b, uf)] = 1;
				}
			}
		}
		for (int a = 0; a < m; a++) {
			delete[] grid[a];
		}
		delete[] grid;
		return res;
	}
	if (i > j) {
		if (i & 1) return visible[0][0];
		string res(100, '0');
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < m; b++) {
				if (b <= 2) res[50*a+b] = visible[b][a][0];
				else res[50*a+b] = visible[2][0][50*a+b-2];
			}
		}
		return res;
	}
	if (j & 1) return visible[0][0];
	string res(100, '0');
	for (int a = 0; a < 2; a++) {
		for (int b = 0; b < m; b++) {
			if (b <= 2) res[50*a+b] = visible[a][b][0];
			else res[50*a+b] = visible[0][2][50*a+b-2];
		}
	}
	return res;
}

• 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