Submission #584632

#	Time	Username	Problem	Language	Result	Execution time	Memory
584632		rainboy	Mars (APIO22_mars)	C++17	100 / 100	1442 ms	4716 KiB

mars

#include "mars.h"
#include <string.h>
#include <stdio.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]));
}
 
int join(int *ds, int i, int j) {
	i = find(ds, i);
	j = find(ds, j);
	if (i == j)
		return 0;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
	return 1;
}
 
string process(vvs ss, int i, int j, int k, int n) {
	int n_ = (k + 1) * 2 + 1, m = (n + 1) / 2, l = (m + 1) / 3;
	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 {
		if (k < l) {
			string s(100, '0');
			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 < m - 1) {
			for (int i1 = 0; i1 < 2; i1++)
				for (int j1 = 0; j1 < 2; j1++)
					for (int i2 = 0; i2 < 3; i2++)
						for (int j2 = 0; j2 < 3; j2++)
							if (i == i1 * (n - m) * 2 + i2 * (m - 1 - k) && j == j1 * (n - m) * 2 + j2 * (m - 1 - k))
								return ss[i2][j2];
			return ss[0][0];
		} else if (k == m - 1) {
			int i0, j0;
			for (i0 = 0; i0 < 2; i0++)
				for (j0 = 0; j0 < 2; j0++)
					if (i == i0 * (n - m) * 2 && j == j0 * (n - m) * 2)
						goto out;
out:
			if (i0 == 2)
				return ss[0][0];
			int m_ = m * 2 + 1, l_ = l * 2 + 1;
			string s_(m_ * m_, '0');
			for (int i1 = 0; i1 < 3; i1++)
				for (int j1 = 0; j1 < 3; j1++)
					for (int i2 = 0; i2 < l_; i2++)
						for (int j2 = 0; j2 < l_; j2++)
							s_[(i1 * (m - l) + i2) * m_ + (j1 * (m - l) + j2)] = ss[i1][j1][i2 * l_ + j2];
			string s((n + 1) * (n + 1), '0');
			for (i = 0; i <= n; i++)
				for (j = 0; j <= n; j++)
					s[i * (n + 1) + j] = s_[(i + i0 * n % 2) * m_ + (j + j0 * n % 2)];
			int ds[(N + 1) * (N + 1)];
			memset(ds, -1, (n + 1) * (n + 1) * sizeof *ds);
			for (i = 0; i <= n; i++)
				for (j = 0; j <= n; j++)
					if (s[i * (n + 1) + j] == '1') {
						if (i > 0 && s[(i - 1) * (n + 1) + j] == '1')
							join(ds, i * (n + 1) + j, (i - 1) * (n + 1) + j);
						if (j > 0 && s[i * (n + 1) + (j - 1)] == '1')
							join(ds, i * (n + 1) + j, i * (n + 1) + (j - 1));
					}
			int rr_[N * 4];
			for (i = 0, j = 0; i < n; i++)
				rr_[i] = find(ds, i * (n + 1) + j);
			for (i = n, j = 0; j < n; j++)
				rr_[n + j] = find(ds, i * (n + 1) + j);
			for (i = n, j = n; i > 0; i--)
				rr_[n * 3 - i] = find(ds, i * (n + 1) + j);
			for (i = 0, j = n; j > 0; j--)
				rr_[n * 4 - j] = find(ds, i * (n + 1) + j);
			int c = 0;
			for (i = 0; i < (n + 1) * (n + 1); i++)
				if (ds[i] < 0 && s[i] == '1')
					c++;
			string t(100, '0');
			int rr[N_];
			if (i0 == 0 && j0 == 0)
				for (int h = 0; h <= n * 2; h++)
					rr[h] = rr_[(h + n) % (n * 4)];
			else if (i0 == 0 && j0 == 1)
				for (int h = 0; h <= n * 2; h++)
					rr[h] = rr_[(h + 0) % (n * 4)];
			else if (i0 == 1 && j0 == 1)
				for (int h = 0; h <= n * 2; h++)
					rr[h] = rr_[(h + n * 3) % (n * 4)];
			else
				for (int h = 0; h <= n * 2; h++)
					rr[h] = rr_[(h + n * 2) % (n * 4)];
			for (int h = 0; h <= n; h++)
				if (s[rr[h]] == '0')
					c++;
			if (i0 == 0 && j0 == 0 && s[rr[n]] == '0')
				c--;
			char used[(N + 1) * (N + 1)];
			for (int h = 0; h < 10; h++)
				t[h] = (c >> h & 1) + '0';
			memset(used, 0, sizeof used);
			for (int h = 0; h <= n * 2; h++)
				if (!used[rr[h]])
					used[rr[h]] = 1, t[10 + (h << 1 | 0)] = '1';
			memset(used, 0, sizeof used);
			for (int h = n * 2; h >= 0; h--)
				if (!used[rr[h]])
					used[rr[h]] = 1, t[10 + (h << 1 | 1)] = '1';
			return t;
		} 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 ds[N_ * 4], qu[N_];
			int c_, cnt;
 
			memset(ds, -1, n_ * 4 * sizeof *ds);
			c_ = 0;
			for (int i0 = 0; i0 < 2; i0++)
				for (int j0 = 0; j0 < 2; j0++) {
					string t = ss[i0 * 2][j0 * 2];
					int g = 0;
					if (i0 == 0 && j0 == 0)
						g = 0;
					else if (i0 == 0 && j0 == 1)
						g = 1;
					else if (i0 == 1 && j0 == 1)
						g = 2;
					else
						g = 3;
					int c = 0;
					for (int h = 0; h < 10; h++)
						if (t[h] == '1')
							c |= 1 << h;
					c_ += c;
					cnt = 0;
					for (int h = 0; h <= n * 2; h++) {
						if (t[10 + (h << 1 | 0)] == '1')
							qu[cnt++] = g * n_ + h;
						else
							join(ds, qu[cnt - 1], g * n_ + h);
						if (t[10 + (h << 1 | 1)] == '1')
							cnt--;
					}
				}
			for (int g = 0; g < 4; g++)
				for (int h = n; h <= n * 2; h++)
					if (join(ds, g * n_ + h, (g + 1) % 4 * n_ + n_ - 1 - h))
						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: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11