Submission #584584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
584584	2022-06-27T15:02:31 Z	rainboy	Mars (APIO22_mars)	C++17	29 / 100	90 ms	2836 KB

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) {
	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) {
			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 < 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 {
			string s(n_ * n_, '0');
			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.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct

Subtask #5
0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct
29	Runtime error	16 ms	468 KB	Execution killed with signal 6
30	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct
29	Runtime error	16 ms	468 KB	Execution killed with signal 6
30	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct
29	Runtime error	16 ms	468 KB	Execution killed with signal 6
30	Halted	0 ms	0 KB	-

Subtask #8
0.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct
29	Runtime error	16 ms	468 KB	Execution killed with signal 6
30	Halted	0 ms	0 KB	-

Subtask #9
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct
29	Runtime error	16 ms	468 KB	Execution killed with signal 6
30	Halted	0 ms	0 KB	-

Subtask #10
0.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1956 KB	Output is correct
2	Correct	7 ms	2052 KB	Output is correct
3	Correct	8 ms	1828 KB	Output is correct
4	Correct	8 ms	1860 KB	Output is correct
5	Correct	7 ms	2152 KB	Output is correct
6	Correct	8 ms	1828 KB	Output is correct
7	Correct	9 ms	2024 KB	Output is correct
8	Correct	16 ms	2224 KB	Output is correct
9	Correct	16 ms	2032 KB	Output is correct
10	Correct	16 ms	2076 KB	Output is correct
11	Correct	16 ms	1860 KB	Output is correct
12	Correct	16 ms	2116 KB	Output is correct
13	Correct	16 ms	1872 KB	Output is correct
14	Correct	27 ms	2420 KB	Output is correct
15	Correct	41 ms	2540 KB	Output is correct
16	Correct	39 ms	2576 KB	Output is correct
17	Correct	41 ms	2512 KB	Output is correct
18	Correct	41 ms	2552 KB	Output is correct
19	Correct	41 ms	2524 KB	Output is correct
20	Correct	40 ms	2536 KB	Output is correct
21	Correct	62 ms	2564 KB	Output is correct
22	Correct	90 ms	2672 KB	Output is correct
23	Correct	88 ms	2700 KB	Output is correct
24	Correct	88 ms	2684 KB	Output is correct
25	Correct	89 ms	2836 KB	Output is correct
26	Correct	89 ms	2688 KB	Output is correct
27	Correct	86 ms	2696 KB	Output is correct
28	Correct	84 ms	2752 KB	Output is correct
29	Runtime error	16 ms	468 KB	Execution killed with signal 6
30	Halted	0 ms	0 KB	-

Submission #584584

Compilation message