Submission #984021

#	Time	Username	Problem	Language	Result	Execution time	Memory
984021		vjudge1	Mars (APIO22_mars)	C++17	14 / 100	16 ms	4652 KiB

mars

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

using namespace std;

const int N = 100;

bool a[N][N];

void clear() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			a[i][j] = false;
}

void colour(int i, int j, int k, string s) {
	for (int x = 0; x < 100; x++) {
		a[i + x / (2 * k + 1)][j + x % (2 * k + 1)] |= (s[x] == '1');
	}
}

string decode(int i, int j, int k) {
	string s;
	for (int x = 0; x <= 2 * k; x++) {
		for (int y = 0; y <= 2 * k; y++) {
			s += a[i + x][j + y] ? '1' : '0';
		}
	}
	while ((int)s.size() < 100) s += '0';
	assert((int)s.size() == 100);
	return s;
}

int bfs() {
	vector<pair<int, int>> dirs = {{-1, 0}, {+1, 0}, {0, -1}, {0, +1}};
	auto move = [&](pair<int, int> s, int i) -> pair<int, int> {
		assert(0 <= i && i < 4);
		return {s.first + dirs[i].first, s.second + dirs[i].second};
	};
	auto check = [&](pair<int, int> b) -> bool {
		return (0 <= b.first && b.first < N && 0 <= b.second && b.second < N && a[b.first][b.second]);
	};

	bool us[N][N] = {};

	int cnt = 0;
	queue<pair<int, int>> q;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (us[i][j] || !a[i][j]) continue;
			cnt++;
			us[i][j] = true;
			q.push({i, j});
			while (!q.empty()) {
				pair<int, int> s = q.front();
				q.pop();
				for (auto d = 0; d < 4; d++) {
					auto next = move(s, d);
					if (check(next) && !us[next.first][next.second]) {
						us[next.first][next.second] = true;
						q.push(next);
					}
				}
			}
		}
	}
	return cnt;
}

string process(vector <vector<string>> a, int i, int j, int k, int n) {
	clear();
	for (int r1 = 0; r1 < 3; r1++) {
		for (int c1 = 0; c1 < 3; c1++) {
			colour(i + r1, j + c1, k, a[r1][c1]);
		}
	}
	if (k != n - 1) 
		return decode(i, j, k + 1);
	int ans = bfs();
	string res(100, '0');
	for (int i = 0; i < 30; i++) {
		res[i] = ((ans >> i & 1) ? '1' : '0');
	}
	return res;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 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