Submission #1225122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225122		PanosPask	Mars (APIO22_mars)	C++20	0 / 100	0 ms	3272 KiB

mars

#include "mars.h"
#include <algorithm>
#define pb push_back

using namespace std;

const int LEN = 100;

const int d_i[4] = {1, 0, -1, 0};
const int d_j[4] = {0, 1, 0, -1};

int N;
vector<vector<bool>> grid;
vector<vector<bool>> visited;

void decode(string& h) {
	grid.resize(N, vector<bool>(N));
	visited.assign(N, vector<bool>(N, false));

	int t = 0;
	for (int k = 0; k < N; k++) {
		int j = N - 1 - k;
		for (int i = N - 1; i >= j; i--) {
			grid[i][j] = h[t] - '0';
			t++;
		}

		int i = N - 1 - k;
		for (int j = i + 1; j < N; j++) {
			grid[i][j] = h[t] - '0';
			t++;
		}
	}
}

void floodfill(int i, int j) {
	if (visited[i][j] || !grid[i][j]) {
		return;
	}

	visited[i][j] = true;

	for (int d = 0; d < 4; d++) {
		int n_i = i + d_i[d];
		int n_j = j + d_j[d];

		if (0 <= min(n_i, n_j) && max(n_i, n_j) < N) {
			floodfill(n_i, n_j);
		}
	}
}

string process(vector<vector<string>> a, int i, int j, int k, int n)
{
	int side = 2 * n + 1;
	if (side * side > LEN) {
		return {};
	}

	if (max(i, j) != 2 * (n - k - 1)) {
		return a[0][0];
	}

	char state = a[0][0][0];
	if (i > j) {
		int prv = 2 * n - (i + 2) + 1;
		a[0][0] = a[2][0];
		a[0][0][prv] = a[1][0][0];
		a[0][0][prv + 1] = state;
	}
	else if (j > i) {
		int prv = 2 * n - (j + 2) + 1;
		a[0][0] = a[0][2];
		a[0][0][prv] = a[0][1][0];
		a[0][0][prv + 1] = state;
	}
	else {
		int len = (2 * n - (i + 2) + 1);
		int pos = len * len;
		
		a[0][0] = a[2][2];

		for (int i = 0; i < len; i++) {
			a[0][0][pos] = a[2][1][i];
			pos++;
		}
		a[0][0][pos] = a[1][1][0];
		pos++;

		for (int i = 0; i < len; i++) {
			a[0][0][pos] = a[1][2][i];
			pos++;
		}

		pos = pos + 3;
		for (int i = 0; i < len; i++) {
			a[0][0][pos] = a[2][0][i];
			pos++;
		}
		a[0][0][pos] = a[1][0][0];
		a[0][0][pos + 1] = state;
		a[0][0][pos + 2] = a[0][1][0];
		
		pos = pos + 3;
		for (int i = 0; i < len; i++) {
			a[0][0][pos] = a[0][2][i];
		}
	}

	if (i != 0 || j != 0) {
		return a[0][0];
	}

	N = 2 * n + 1;
	decode(a[0][0]);

	int cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (visited[i][j] == false && grid[i][j]) {
				cnt++;
				floodfill(i, j);
			}
		}
	}

	a[0][0].clear();
	while (cnt) {
		a[0][0].pb((cnt % 2) + '0');
		cnt /= 2;
	}
	a[0][0].resize(100, '0');

	return a[0][0];
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 7
• Subtask 6: 0 / 8
• Subtask 7: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11