Submission #1225341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225341		Jer	Mars (APIO22_mars)	C++20	0 / 100	214 ms	3320 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>

using namespace std;

#define coord(y, x, n) ((y * (2 * n + 1)) + x)

string make(vector<vector<string>> a, int i, int j, int n){
	string res(100, '0');

	for (int y = 0; y < 3; y++)
		for (int x = 0; x < 3; x++) if (a[y][x][0] == '1')
			res[coord((i + y), (j + x), n)] = '1';
	
	return res;
}

string makea(vector<vector<string>> a){
	string res = a[0][0];

	for (int y = 0; y < 3; y++)
		for (int x = 0; x < 3; x++)
			for (int d = 0; d < 100; d++) if (res[d] == '0' and a[y][x][d] == '1')
				res[d] = '1';
	
	return res;
}

int get(vector<vector<int>> b, int i, int j, int n){
	if (i < 0 or j < 0 or i >= 2 * n + 1 or j >= 2 * n + 1) return -1;
	return b[i][j];
}

#define isn(b, i, j, n) (get(b, i + 1, j, n) == 2 or get(b, i, j + 1, n) == 2 or get(b, i - 1, j, n) == 2 or get(b, i, j - 1, n) == 2)

int dfs(vector<vector<int>> b, int i, int j, int n, bool t){
	if (i < 0 or j < 0 or i >= (2 * n + 1) or j >= (2 * n + 1)) return 0;
	if (b[i][j] == 0){
		int res = 0;
		b[i][j] = 2;
		res += dfs(b, i + 1, j, n, t);
		res += dfs(b, i, j + 1, n, t);
		res += dfs(b, i - 1, j, n, t);
		res += dfs(b, i, j - 1, n, t);
		return res;
	}
	if (b[i][j] == 2) return 0;
	if (t and b[i][j] == 1){
		b[i][j] = 2;
		dfs(b, i + 1, j, n, t);
		dfs(b, i, j + 1, n, t);
		dfs(b, i - 1, j, n, t);
		dfs(b, i, j - 1, n, t);
		return 0;
	}
	if (not t and b[i][j] == 1)
	{
		b[i][j] = 2;
		dfs(b, i + 1, j, n, true);
		dfs(b, i, j + 1, n, true);
		dfs(b, i - 1, j, n, true);
		dfs(b, i, j - 1, n, true);
		return 1;
	}
}

int count(vector<vector<int>> b, int n){
	return dfs(b, 0, 0, n, false);
}

string to_binary(int x){
	string res;

	while (x > 0)
		res.push_back(x % 2 + '0'), x /= 2;
	res.push_back(x % 2 + '0');

	while (res.size() < 100)
		res.push_back('0');
	
	return res;
}

std::string process(std::vector <std::vector<std::string>> a, int i, int j, int k, int n)
{
	if (n == 1){
		vector<vector<int>> b(2 * n + 1);
		for (int i = 0; i < 2 * n + 1; i++) b[i].resize(2 * n + 1);
		string l = make(a, i, j, n);
	
		for (int i = 0; i < 2 * n + 1; i++)
			for (int j = 0; j < 2 * n + 1; j++)
				b[i][j] = l[coord(i, j, n)] - '0';
		
		return to_binary(count(b, n));
	}

	if (k == 0)
		return make(a, i, j, n);
	
	if (k != n - 1)
		return makea(a);
	
	vector<vector<int>> b(2 * n + 1);
	for (int i = 0; i < 2 * n + 1; i++) b[i].resize(2 * n + 1);

	string l = makea(a);
	
	for (int i = 0; i < 2 * n + 1; i++)
		for (int j = 0; j < 2 * n + 1; j++)
			b[i][j] = l[coord(i, j, n)] - '0';
	
	return to_binary(count(b, n));
}

Compilation message (stderr)

mars.cpp: In function 'int dfs(std::vector<std::vector<int> >, int, int, int, bool)':
mars.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
   65 | }
      | ^

• 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