Submission #1103773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103773		fve5	Mars (APIO22_mars)	C++17	44 / 100	348 ms	4900 KiB

mars

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

#define SIZE 100
#define MAXL 45

string collect(const vector<vector<string>> &a, int k) {
	string ans;
	for (int i = 0; i < 2 * k + 3; i++) {
		if (i < 2 * k + 1) {
			ans += a[0][0].substr(i * (2 * k + 1), 2 * k + 1) + a[0][1][i * (2 * k + 1) + 2 * k] + a[0][2][i * (2 * k + 1) + 2 * k];
		} else {
			int j = i - 2 * k;
			ans += a[j][0].substr((2 * k) * (2 * k + 1), 2 * k + 1) + a[j][1][(2 * k) * (2 * k + 1) + 2 * k] + a[j][2][(2 * k) * (2 * k + 1) + 2 * k];
		}
	}
	
	return ans + string(SIZE - ans.size(), '0');
}

vector<vector<map<int, int>>> get_trans(int n) {
	vector<vector<map<int, int>>> trans(2 * n + 1, vector<map<int, int>>(2 * n + 1));
	int sz = 2 * n + 1;

	for (int x = 0; ; x++) {
		int sx = max(0, sz - 9 * (x + 1));
		int tx = sx == 0 ? 0 : 2 - x;

		for (int y = 0; ; y++) {
			int sy = max(0, sz - 9 * (y + 1));
			int ty = sy == 0 ? 0 : 2 - y;

			int cnt = 0, cx = sx, cy = sy;
			while (cx != tx || cy != ty) {
				int nx = cx - 2 * (cx != tx);
				int ny = cy - 2 * (cy != ty);

				trans[nx][ny][cnt] = ((cx != tx) << 1) | (cy != ty);

				cx = nx;
				cy = ny;
				cnt++;
			}

			if (sy == 0) break;
		}
		if (sx == 0) break;
	}

	return trans;
}

int last_call(int n, int i, int j) { return min((2 * n - i) / 2, (2 * n - j) / 2) - 1; }

string transfer(const vector<vector<string>> &a, int i, int j, int k, int n) {
	switch (get_trans(n)[i][j][k - 4]) {
		case 0: return a[0][0];
		case 1: return a[0][2];
		case 2: return a[2][0];
		case 3: return a[2][2];
	}
}

string cc(const vector<vector<string>> &a, int n) {
	int sz = 2 * n + 1;
	vector<vector<bool>> grid(sz, vector<bool>(sz));

	if (n > 4) {
		for (int x = 0; ; x++) {
			int sx = max(0, sz - 9 * (x + 1));
			int tx = sx == 0 ? 0 : 2 - x;

			for (int y = 0; ; y++) {
				int sy = max(0, sz - 9 * (y + 1));
				int ty = sy == 0 ? 0 : 2 - y;

				int w = sy == 0 ? (sz - 1) % 9 + 1 : 9;
				int h = sx == 0 ? (sz - 1) % 9 + 1 : 9;

				for (int i = 0; i < h; i++) {
					for (int j = 0; j < w; j++) {
						grid[sx + i][sy + j] = a[tx][ty][i * 9 + j] == '1';
					}
				}

				if (sy == 0) break;
			}
			if (sx == 0) break;
		}
	} else {
		string g = collect(a, n - 1);
		for (int i = 0; i < sz; i++)
			for (int j = 0; j < sz; j++)
				grid[i][j] = g[sz * i + j] == '1';
	}

	vector<vector<bool>> vis(sz, vector<bool>(sz));

	int cnt = 0;
	for (int i = 0; i < sz; i++) {
		for (int j = 0; j < sz; j++) {
			if (vis[i][j] || !grid[i][j]) continue;

			cnt++;
			queue<pair<int, int>> q;
			q.emplace(i, j);

			while (!q.empty()) {
				auto [x, y] = q.front(); q.pop();
				if (vis[x][y] || !grid[x][y]) continue;
				vis[x][y] = true;

				if (x > 0)
					q.emplace(x - 1, y);
				if (x < sz - 1)
					q.emplace(x + 1, y);
				if (y > 0)
					q.emplace(x, y - 1);
				if (y < sz - 1)
					q.emplace(x, y + 1);
			}
		}
	}

	string ans(SIZE, '0');
	for (int i = 0; i < SIZE; i++) {
		if (cnt & 1)
			ans[i] = '1';
		cnt >>= 1;
	}
	return ans;
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
	if (k == n - 1)
		return cc(a, n);
	if (k <= 3)
		return collect(a, k);

	return transfer(a, i, j, k, n);
	
	assert(false);
}

Compilation message (stderr)

mars.cpp: In function 'std::string transfer(const std::vector<std::vector<std::__cxx11::basic_string<char> > >&, int, int, int, int)':
mars.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
   63 | }
      | ^

• 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: 0 / 10
• Subtask 8: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11