Submission #726205

#	Time	Username	Problem	Language	Result	Execution time	Memory
726205		hollwo_pelw	Mars (APIO22_mars)	C++17	100 / 100	3395 ms	5700 KiB

mars

#include "mars.h"

#ifdef hollwo_pelw_local
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;

const int N = 50;

#define pii pair<int, int> 
#define x first
#define y second

bool board[N][N];
int vis[N][N];
vector<pii> adj[N][N]; // boundary of 4 corners

const int dx[] = {-1, 0, +1, 0};
const int dy[] = {0, -1, 0, +1};

void dfs(int x, int y) {
	for (int d = 0; d < 4; d++) {
		int nx = x + dx[d], ny = y + dy[d];
		if (nx < 0 || ny < 0) continue;
		if (board[nx][ny] && vis[nx][ny] == -1)
			vis[nx][ny] = vis[x][y], dfs(nx, ny);
	}

	for (auto [nx, ny] : adj[x][y]) {
		if (board[nx][ny] && vis[nx][ny] == -1)
			vis[nx][ny] = vis[x][y], dfs(nx, ny);
	}
}

int decode(const string &s) {
	int v = 0, len = s.size();
	for (int i = 0; i < min(20, len); i++)
		v |= (s[i] == '1') << i;
	return v;
}

int decode(const string &s, int p, int len) {
	return decode(s.substr(p, len));
}

string encode(int len, int v) {
	// cout << "encode " << len << ' ' << v << '\n';
	string res(len, '0');
	for (int i = 0; i < min(20, len); i++)
		res[i] = "01"[v >> i & 1];
	// cout << res << '\n';
	return res;
}

string process(vector<vector<string>> s, int i, int j, int k, int n) {
	memset(vis, -1, sizeof vis);
	memset(board, 0, sizeof board);

	for (int i = 0; i <= 2 * n; i++) {
		for (int j = 0; j <= 2 * n; j++)
			adj[i][j].clear();
	}

	if (n == 1) {
		for (int i = 0; i <= 2 * n; i++) {
			for (int j = 0; j <= 2 * n; j++) {
				board[i][j] = s[i][j][0] == '1';
			}
		}

		int res = 0;
		for (int i = 0; i <= 2 * n; i++) for (int j = 0; j <= 2 * n; j++) {
			if (board[i][j] && vis[i][j] == -1) {
				vis[i][j] = res ++, dfs(i, j);
			}
		}

		return encode(100, res);

	}

	pii cur[N][N], nxt[N][N];

	// cout << "PHRASE " << n << ' ' << k << " -> " << "x = " << i << ' ' << "y = " << j << '\n';

	for (int x = 0; x <= 2 * n; x++) {
		for (int y = 0; y <= 2 * n; y++) {
			cur[x][y] = {min(x * n / 2, x + 2 * k)      , min(y * n / 2, y + 2 * k)      };
			nxt[x][y] = {min(x * n / 2, x + 2 * (k + 1)), min(y * n / 2, y + 2 * (k + 1))};
			// cout << x << ' ' << y << " -> " << nxt[x][y].x << ' ' << nxt[x][y].y << '\n';
		}
	}

	vector<pii> bound[4];
	for (int i = 0; i <= n; i++) {
		bound[0].push_back({n, i});
		bound[1].push_back({n, n * 2 - i});
		bound[2].push_back({n, i});
		bound[3].push_back({n, n * 2 - i});
	}
	for (int i = 1; i <= n; i++) {
		bound[0].push_back({n - i, n});
		bound[1].push_back({n - i, n});
		bound[2].push_back({n + i, n});
		bound[3].push_back({n + i, n});
	}

	if (k == n - 1) {
		// solve last step
		int res = 0;
		for (int fx : {0, 2}) for (int fy : {0, 2}) {
			auto curbound = bound[fx + fy / 2];

			string mask = s[fx][fy].substr(0, 41);
			string A = s[fx][fy].substr(41, 21);
			string B = s[fx][fy].substr(62, 21);
			res += decode(s[fx][fy], 83, 17);

			// cout << s[fx][fy].substr(83, 17) << '\n';
			// cout << res << '\n';

			vector<int> comp;
			for (int i = 0; i <= 2 * n; i++) {
				if (mask[i] & 1) {
					auto [x, y] = curbound[i];
					board[x][y] = 1;
				}
				if ((mask[i] & 1) && (i == 0 || !(mask[i - 1] & 1)))
					comp.push_back(i);
			}

			vector<int> stk;

			// cout << "CORNER " << fx << ' ' << fy << '\n';

			for (int i = 0, m = comp.size(); i < m; i++) {
				if (A[i] & 1) {
					stk.push_back(i);
				} else {
					auto [x1, y1] = curbound[comp[stk.back()]];
					auto [x2, y2] = curbound[comp[i]];


					// cout << x1 << ' ' << y1 << " -> " << x2 << ' ' << y2 << '\n';

					adj[x1][y1].push_back({x2, y2});
					adj[x2][y2].push_back({x1, y1});
				}

				if (B[i] & 1) {
					stk.pop_back();
				}
			}
		}

		for (int i = 0; i <= 2 * n; i++) for (int j = 0; j <= 2 * n; j++) {
			if (board[i][j] && vis[i][j] == -1) {
				vis[i][j] = ++ res, dfs(i, j);
			}
		}

		return encode(100, res);
	}
	if (k == n - 2) {
		// solve second last
		if (i % 2 == 1 || j % 2 == 1)
			return string(100, '0');
		auto curbound = bound[i + j / 2];
		int xl = 0, xr = n, yl = 0, yr = n;
		if (i) xl += n, xr += n;
		if (j) yl += n, yr += n;

		// for (int i = 0; i < 3; i++) {
		// 	for (int j = 0; j < 3; j++)
		// 		cout << s[i][j] << '\n';
		// }

		for (int x = xl; x <= xr; x++) for (int y = yl; y <= yr; y++) {
			bool ok = 0;
			for (int fx = 3; fx --; ) for (int fy = 3; fy -- && !ok; ) {
				int ox = x - cur[i + fx][j + fy].x;
				int oy = y - cur[i + fx][j + fy].y;
				if (ox < 0 || oy < 0 || ox >= 10 || oy >= 10)
					continue;
				// cout << x << ' ' << y << " keep in " << ox << ' ' << oy << '\n';
				// cout << "-> " << s[fx][fy][ox * 10 + oy] << '\n';
				board[x][y] = s[fx][fy][ox * 10 + oy] == '1', ok = 1;
			}
			// cout << board[x][y];
			// if (y == yr) cout << '\n';
		}

		int cnt_oth = 0, cnt_bnd = 0;

		for (auto [x, y] : curbound) {
			if (board[x][y] && vis[x][y] == -1) {
				vis[x][y] = ++ cnt_bnd, dfs(x, y);
			}
		}

		// for (int x = xl; x <= xr; x++) for (int y = yl; y <= yr; y++) {
		// 	cout << vis[x][y] << "\t\n"[y == yr];
		// }

		for (int x = xl; x <= xr; x++) for (int y = yl; y <= yr; y++) {
			if (board[x][y] && vis[x][y] == -1)
				vis[x][y] = ++ cnt_oth, dfs(x, y);
		}

		// cout << cnt_bnd << '\n';
		// cout << cnt_oth << '\n';

		assert((int) curbound.size() == 2 * n + 1);

		string mask(41, '0'), A(21, '0'), B(21, '0');
		
		vector<pair<int, int>> comp;

		for (int i = 0; i <= 2 * n; i++) {
			auto [x, y] = curbound[i];
			mask[i] = "01"[board[x][y]];
			if ((mask[i] & 1) && (i == 0 || !(mask[i - 1] & 1)))
				comp.push_back({i, vis[x][y]});
			// cout << mask[i];
		}
		// cout << '\n';

		for (int i = 0, m = comp.size(); i < m; i++) {
			bool isA = 1, isB = 1;
			for (int j = 0; j < i; j++)
				isA &= comp[j].second != comp[i].second;
			for (int j = i + 1; j < m; j++)
				isB &= comp[j].second != comp[i].second;
			A[i] = "01"[isA], B[i] = "01"[isB];
		}

		// cout << comp.size() << "\n";
		// cout << mask << "\n" << A << "\n" << B << "\n";

		// mask = component
		// A = open bracket
		// B = close bracket
		return mask + A + B + encode(17, cnt_oth);
	}
	// solve other case
	
	// cout << cur[2][3].x << ' ' << cur[2][3].y << '\n';
	// cout << nxt[2][3].x << ' ' << nxt[2][3].y << '\n';

	string res(100, '0');
	for (int x = 0; x < 10; x++) for (int y = 0; y < 10; y++) {
		bool ok = 0;
		for (int fx = 3; fx --; ) for (int fy = 3; fy -- && !ok; ) {
			int ox = x + nxt[i][j].x - cur[i + fx][j + fy].x;
			int oy = y + nxt[i][j].y - cur[i + fx][j + fy].y;

			if (ox < 0 || ox >= 10 || oy < 0 || oy >= 10)
				continue;

			res[x * 10 + y] = s[fx][fy][ox * 10 + oy], ok = 1;
			// cout << "KEEP " << x << ' ' << y << " = " << res[x * 10 + y] << '\n';
		}
	}


	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