Submission #584582

#	Time	Username	Problem	Language	Result	Execution time	Memory
584582		rainboy	Mars (APIO22_mars)	C++17	14 / 100	18 ms	2360 KiB

mars

#include "mars.h"
#include <string.h>

using namespace std;

typedef vector<string> vs;
typedef vector<vs> vvs;

const int N = 20, N_ = N * 2 + 1;

int find(int *ds, int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}

void join(int *ds, int i, int j) {
	i = find(ds, i);
	j = find(ds, j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

string process(vvs ss, int i, int j, int k, int n) {
	string s(100, '0');
	int n_ = (k + 1) * 2 + 1;
	if (n == 1) {
		int ds[N_ * N_];
		memset(ds, -1, n_ * n_ * sizeof *ds);
		for (i = 0; i < n_; i++)
			for (j = 0; j < n_; j++)
				if (ss[i][j][0] == '1') {
					if (i > 0 && ss[i - 1][j][0] == '1')
						join(ds, i * n_ + j, (i - 1) * n_ + j);
					if (j > 0 && ss[i][j - 1][0] == '1')
						join(ds, i * n_ + j, i * n_ + (j - 1));
				}
		int c = 0;
		for (i = 0; i < n_ * n_; i++)
			if (ds[i] < 0 && ss[i / n_][i % n_][0] == '1')
				c++;
		string t(100, '0');
		for (int h = 0; h < 10; h++)
			t[h] = (c >> h & 1) + '0';
		return t;
	} else {
		int m = (n + 1) / 2;
		if (k < m) {
			for (int i1 = 0; i1 < 3; i1++)
				for (int j1 = 0; j1 < 3; j1++)
					for (int i2 = 0; i2 < n_ - 2; i2++)
						for (int j2 = 0; j2 < n_ - 2; j2++)
							s[(i1 + i2) * n_ + (j1 + j2)] = ss[i1][j1][i2 * (n_ - 2) + j2];
			return s;
		} else if (k < n - 1) {
			if (i == (n - 1 - k) * 2 && j == 0)
				return ss[2][0];
			else if (i == 0 && j == (n - 1 - k) * 2)
				return ss[0][2];
			if (i == (n - 1 - k) * 2 && j == (n - 1 - k) * 2)
				return ss[2][2];
			return ss[0][0];
		} else {
			int m_ = m * 2 + 1;
			for (int i1 = 0; i1 < 3; i1 += 2)
				for (int j1 = 0; j1 < 3; j1 += 2)
					for (int i2 = 0; i2 < m_; i2++)
						for (int j2 = 0; j2 < m_; j2++)
							s[(i1 * (n - m) + i2) * n_ + (j1 * (n - m) + j2)] = ss[i1][j1][i2 * m_ + j2];
			int ds[N_ * N_];
			memset(ds, -1, n_ * n_ * sizeof *ds);
			for (i = 0; i < n_; i++)
				for (j = 0; j < n_; j++)
					if (s[i * n_ + j] == '1') {
						if (i > 0 && s[(i - 1) * n_ + j] == '1')
							join(ds, i * n_ + j, (i - 1) * n_ + j);
						if (j > 0 && s[i * n_ + (j - 1)] == '1')
							join(ds, i * n_ + j, i * n_ + (j - 1));
					}
			int c = 0;
			for (i = 0; i < n_ * n_; i++)
				if (ds[i] < 0 && s[i] == '1')
					c++;
			string t(100, '0');
			for (int h = 0; h < 10; h++)
				t[h] = (c >> h & 1) + '0';
			return t;
		}
	}
}

• 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