oj.uz

Submission #584623

# Submission time Handle Problem Language Result Execution time Memory
584623 2022-06-27T17:20:49 Z rainboy Mars (APIO22_mars) C++17
14 / 100
 16 ms 2148 KB 
#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_ * N_];
			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 * 4];
			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 * 2 + 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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1952 KB Output is correct
2 Correct 8 ms 1688 KB Output is correct
3 Correct 8 ms 1904 KB Output is correct
4 Correct 8 ms 1784 KB Output is correct
5 Correct 8 ms 1960 KB Output is correct
6 Correct 8 ms 1780 KB Output is correct
7 Correct 9 ms 2036 KB Output is correct
8 Correct 15 ms 1904 KB Output is correct
9 Correct 15 ms 1960 KB Output is correct
10 Correct 16 ms 2120 KB Output is correct
11 Correct 15 ms 2148 KB Output is correct
12 Correct 16 ms 1900 KB Output is correct
13 Correct 16 ms 2032 KB Output is correct
14 Incorrect 4 ms 328 KB Incorrect
15 Halted 0 ms 0 KB -