oj.uz

답안 #789708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789708 2023-07-21T19:35:55 Z GusterGoose27 화성 (APIO22_mars) C++17
44 / 100
 159 ms 3384 KB 
#include "mars.h"

#include <bits/stdc++.h>

using namespace std;

bool val(string &s, int p = 0) {
	return s[p]-'0';
}

int find(int i, vector<int> &uf) {
	return uf[i] == i ? i : uf[i] = find(uf[i], uf);
}

void merge(int a, int b, vector<int> &uf) {
	a = find(a, uf);
	b = find(b, uf);
	if (a != b) uf[a] = b;
}

/*

BIT ALLOCATION:

For main diag, first bit is for value,
	next 44 bits are for start and then end union find when starting from the bottom,
		going up, and then right
	last 10 bits are for the answer

For off diag, first 50 bits represent going down/right,
	and next 50 bits are down/right one row/column over

*/

string process(vector<vector<string>> visible, int i, int j, int k, int n) {
	if (i < 2*(n-k-1) && j < 2*(n-k-1)) return visible[0][0];
	int m = 2*k+3;
	if (i == j) {
		if (i & 1) return visible[0][0];
		bool **grid;
		grid = new bool*[m];
		for (int a = 0; a < m; a++) {
			grid[a] = new bool[m];
			fill(grid[a], grid[a]+m, 0);
		} // make the grid
		for (int a = 0; a < 3; a++) {
			for (int b = 0; b < 3; b++)
				grid[a][b] = val(visible[a][b]);
		}
		for (int b = 3; b < m; b++) {
			grid[b][0] = val(visible[2][0], b-2);
			grid[b][1] = val(visible[2][1], b-2);
			grid[b][2] = val(visible[2][1], 50+b-2);
			grid[0][b] = val(visible[0][2], b-2);
			grid[1][b] = val(visible[1][2], b-2);
			grid[2][b] = val(visible[1][2], 50+b-2);
		}
		// for (int a = 0; a < m; a++) {
		// 	for (int b = 0; b < m; b++) {
		// 		cerr << grid[a][b] << ' ';
		// 	}
		// 	cerr << '\n';
		// }
		// extract current answer from visible[2][2]
		int ans = 0;
		vector<int> uf(m*m);
		iota(uf.begin(), uf.end(), 0);
		if (m > 3) {
			for (int a = 0; a < 10; a++) {
				ans += (val(visible[2][2], 100-a-1)<<a);
			}
			for (int b = 0; b < m-2; b++) {
				for (int a = 0; a < 2; a++) {
					grid[b+2][1+a] = val(visible[2][1], 50*a+b);
					grid[1+a][b+2] = val(visible[1][2], 50*a+b);
				}
				grid[b+2][0] = val(visible[2][0], b);
				grid[0][b+2] = val(visible[0][2], b);
			}
			vector<int> starts;
			int p = 0;
			// cerr << visible[2][2] << '\n';
			for (int a = m-1; a >= 2; a--) {
				for (int b = 2; b < m; b++) {
					if (a != 2 && b != 2) continue;
					if (!grid[a][b]) continue;
					bool is_start = val(visible[2][2], p+1);
					bool is_end = val(visible[2][2], p+45);
					int cur = m*a+b;
					p++;
					if (is_end) {
						// if (starts.empty()) exit(0);
						assert(starts.size());
						merge(starts.back(), cur, uf);
						starts.pop_back();
						// cerr << "0\n";
					}
					if (is_start) {
						starts.push_back(cur);
						// cerr << "1\n";
					}
				}
			}
			assert(starts.empty());
			for (int a = m-1; a >= 2; a--) {
				for (int b = 2; b < m; b++) {
					if (a != 2 && b != 2) continue;
					if (!grid[a][b]) continue;
					int cur = m*a+b;
					ans -= (uf[cur] == cur); // this cc is currently represented
				}
			}
		}
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < m; b++) {
				if (a < m-1 && grid[a][b] && grid[a+1][b]) merge(m*a+b, m*a+b+m, uf);
				if (b < m-1 && grid[a][b] && grid[a][b+1]) merge(m*a+b, m*a+b+1, uf);
			}
		}
		for (int a = 0; a < m; a++) {
			for (int b = 0; b < m; b++) {
				ans += (grid[a][b] && uf[m*a+b] == m*a+b);
			}
		}
		string res(100, '0');
		res[0] = visible[0][0][0];
		if (i == 0) {
			int p = 0;
			while (ans) {
				res[p] = '0'+(ans&1);
				ans /= 2;
				p++;
			}
		}
		else {
			for (int p = 0; p < 10; p++, ans /= 2) res[100-p-1] = '0'+(ans&1);
			vector<char> seen(m*m, 0);
			int p = 0;
			for (int a = m-1; a >= 0; a--) {
				for (int b = 0; b < m; b++) {
					if (a && b) continue;
					if (!grid[a][b]) continue;
					res[45+p] = '0'+seen[find(m*a+b, uf)];
					seen[find(m*a+b, uf)] = 1;
					p++;
				}
			}
			fill(seen.begin(), seen.end(), 0);
			for (int b = m-1; b >= 0; b--) {
				for (int a = 0; a < m; a++) {
					if (a && b) continue;
					if (!grid[a][b]) continue;
					--p;
					res[1+p] = '0'+seen[find(m*a+b, uf)];
					seen[find(m*a+b, uf)] = 1;
				}
			}
		}
		for (int a = 0; a < m; a++) {
			delete[] grid[a];
		}
		delete[] grid;
		return res;
	}
	if (i > j) {
		if (i & 1) return visible[0][0];
		string res(100, '0');
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < m; b++) {
				if (b <= 2) res[50*a+b] = visible[b][a][0];
				else res[50*a+b] = visible[2][0][50*a+b-2];
			}
		}
		return res;
	}
	if (j & 1) return visible[0][0];
	string res(100, '0');
	for (int a = 0; a < 2; a++) {
		for (int b = 0; b < m; b++) {
			if (b <= 2) res[50*a+b] = visible[a][b][0];
			else res[50*a+b] = visible[0][2][50*a+b-2];
		}
	}
	return res;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct

Subtask #5
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct
29 Correct 69 ms 2780 KB Output is correct
30 Correct 94 ms 2904 KB Output is correct
31 Correct 93 ms 2804 KB Output is correct
32 Correct 96 ms 2844 KB Output is correct
33 Correct 90 ms 2932 KB Output is correct
34 Correct 94 ms 2788 KB Output is correct
35 Correct 89 ms 2816 KB Output is correct
36 Correct 93 ms 2800 KB Output is correct

Subtask #6
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct
29 Correct 69 ms 2780 KB Output is correct
30 Correct 94 ms 2904 KB Output is correct
31 Correct 93 ms 2804 KB Output is correct
32 Correct 96 ms 2844 KB Output is correct
33 Correct 90 ms 2932 KB Output is correct
34 Correct 94 ms 2788 KB Output is correct
35 Correct 89 ms 2816 KB Output is correct
36 Correct 93 ms 2800 KB Output is correct
37 Correct 120 ms 3096 KB Output is correct
38 Correct 146 ms 3264 KB Output is correct
39 Correct 159 ms 3244 KB Output is correct
40 Correct 155 ms 3368 KB Output is correct
41 Correct 148 ms 3272 KB Output is correct
42 Correct 158 ms 3368 KB Output is correct
43 Correct 154 ms 3292 KB Output is correct
44 Correct 158 ms 3384 KB Output is correct

Subtask #7
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct
29 Correct 69 ms 2780 KB Output is correct
30 Correct 94 ms 2904 KB Output is correct
31 Correct 93 ms 2804 KB Output is correct
32 Correct 96 ms 2844 KB Output is correct
33 Correct 90 ms 2932 KB Output is correct
34 Correct 94 ms 2788 KB Output is correct
35 Correct 89 ms 2816 KB Output is correct
36 Correct 93 ms 2800 KB Output is correct
37 Correct 120 ms 3096 KB Output is correct
38 Correct 146 ms 3264 KB Output is correct
39 Correct 159 ms 3244 KB Output is correct
40 Correct 155 ms 3368 KB Output is correct
41 Correct 148 ms 3272 KB Output is correct
42 Correct 158 ms 3368 KB Output is correct
43 Correct 154 ms 3292 KB Output is correct
44 Correct 158 ms 3384 KB Output is correct
45 Runtime error 24 ms 592 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct
29 Correct 69 ms 2780 KB Output is correct
30 Correct 94 ms 2904 KB Output is correct
31 Correct 93 ms 2804 KB Output is correct
32 Correct 96 ms 2844 KB Output is correct
33 Correct 90 ms 2932 KB Output is correct
34 Correct 94 ms 2788 KB Output is correct
35 Correct 89 ms 2816 KB Output is correct
36 Correct 93 ms 2800 KB Output is correct
37 Correct 120 ms 3096 KB Output is correct
38 Correct 146 ms 3264 KB Output is correct
39 Correct 159 ms 3244 KB Output is correct
40 Correct 155 ms 3368 KB Output is correct
41 Correct 148 ms 3272 KB Output is correct
42 Correct 158 ms 3368 KB Output is correct
43 Correct 154 ms 3292 KB Output is correct
44 Correct 158 ms 3384 KB Output is correct
45 Runtime error 24 ms 592 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct
29 Correct 69 ms 2780 KB Output is correct
30 Correct 94 ms 2904 KB Output is correct
31 Correct 93 ms 2804 KB Output is correct
32 Correct 96 ms 2844 KB Output is correct
33 Correct 90 ms 2932 KB Output is correct
34 Correct 94 ms 2788 KB Output is correct
35 Correct 89 ms 2816 KB Output is correct
36 Correct 93 ms 2800 KB Output is correct
37 Correct 120 ms 3096 KB Output is correct
38 Correct 146 ms 3264 KB Output is correct
39 Correct 159 ms 3244 KB Output is correct
40 Correct 155 ms 3368 KB Output is correct
41 Correct 148 ms 3272 KB Output is correct
42 Correct 158 ms 3368 KB Output is correct
43 Correct 154 ms 3292 KB Output is correct
44 Correct 158 ms 3384 KB Output is correct
45 Runtime error 24 ms 592 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1948 KB Output is correct
2 Correct 6 ms 2052 KB Output is correct
3 Correct 5 ms 2104 KB Output is correct
4 Correct 6 ms 1768 KB Output is correct
5 Correct 6 ms 1948 KB Output is correct
6 Correct 5 ms 1852 KB Output is correct
7 Correct 8 ms 1832 KB Output is correct
8 Correct 8 ms 2024 KB Output is correct
9 Correct 9 ms 1920 KB Output is correct
10 Correct 8 ms 1684 KB Output is correct
11 Correct 8 ms 1688 KB Output is correct
12 Correct 8 ms 2012 KB Output is correct
13 Correct 9 ms 2128 KB Output is correct
14 Correct 17 ms 2548 KB Output is correct
15 Correct 23 ms 2532 KB Output is correct
16 Correct 23 ms 2596 KB Output is correct
17 Correct 23 ms 2488 KB Output is correct
18 Correct 23 ms 2584 KB Output is correct
19 Correct 23 ms 2576 KB Output is correct
20 Correct 23 ms 2496 KB Output is correct
21 Correct 40 ms 2644 KB Output is correct
22 Correct 49 ms 2660 KB Output is correct
23 Correct 48 ms 2680 KB Output is correct
24 Correct 45 ms 2664 KB Output is correct
25 Correct 45 ms 2716 KB Output is correct
26 Correct 52 ms 2724 KB Output is correct
27 Correct 49 ms 2680 KB Output is correct
28 Correct 49 ms 2688 KB Output is correct
29 Correct 69 ms 2780 KB Output is correct
30 Correct 94 ms 2904 KB Output is correct
31 Correct 93 ms 2804 KB Output is correct
32 Correct 96 ms 2844 KB Output is correct
33 Correct 90 ms 2932 KB Output is correct
34 Correct 94 ms 2788 KB Output is correct
35 Correct 89 ms 2816 KB Output is correct
36 Correct 93 ms 2800 KB Output is correct
37 Correct 120 ms 3096 KB Output is correct
38 Correct 146 ms 3264 KB Output is correct
39 Correct 159 ms 3244 KB Output is correct
40 Correct 155 ms 3368 KB Output is correct
41 Correct 148 ms 3272 KB Output is correct
42 Correct 158 ms 3368 KB Output is correct
43 Correct 154 ms 3292 KB Output is correct
44 Correct 158 ms 3384 KB Output is correct
45 Runtime error 24 ms 592 KB Execution killed with signal 6
46 Halted 0 ms 0 KB -