제출 #584559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584559		rainboy	Mars (APIO22_mars)	C++17	14 / 100	16 ms	2248 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;
	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];
	if (k < n - 1)
		return s;
	else {
		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