oj.uz

Submission #725579

# Submission time Handle Problem Language Result Execution time Memory
725579 2023-04-17T17:03:10 Z SanguineChameleon Mars (APIO22_mars) C++17
6 / 100
 8 ms 2224 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
 
string process(vector<vector<string>> a, int cur_i, int cur_j, int cur_k, int n) {
	if (n == 1) {
		const vector<int> dx = {1, -1, 0, 0};
		const vector<int> dy = {0, 0, 1, -1};
		vector<vector<bool>> flag(3);
		for (int i = 0; i < 3; i++) {
			flag[i].resize(3);
		}
		int cnt = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (!flag[i][j] && a[i][j][0] == '1') {
					flag[i][j] = true;
					deque<pair<int, int>> q = {{i, j}};
					cnt++;
					while (!q.empty()) {
						int cx = q.front().first;
						int cy = q.front().second;
						q.pop_front();
						for (int k = 0; k < 4; k++) {
							int nx = cx + dx[k];
							int ny = cy + dy[k];
							if (0 <= nx && nx < 3 && 0 <= ny && ny < 3 && a[nx][ny][0] == '1' && !flag[nx][ny]) {
								flag[nx][ny] = true;
								q.push_back({nx, ny});
							}
						}
					}
				}
			}
		}
		string res;
		while (cnt) {
			res += (char)('0' + (cnt & 1));
			cnt >>= 1;
		}
		res.resize(100, '0');
		return res;
	}
	vector<vector<pair<int, int>>> cur_off, nxt_off;
	cur_off.resize(n * 2 + 2);
	nxt_off.resize(n * 2 + 2);
	for (int i = 0; i < n * 2 + 2; i++) {
		cur_off[i].resize(n * 2 + 2);
		nxt_off[i].resize(n * 2 + 2);
	}
	for (int i = 0; i < n * 2 + 2; i++) {
		for (int j = 0; j < n * 2 + 2; j++) {
			cur_off[i][j] = {min(i * n / 2, i + cur_k * 2), min(j * n / 2, j + cur_k * 2)};
			nxt_off[i][j] = {min(i * n / 2, i + (cur_k + 1) * 2), min(j * n / 2, j + (cur_k + 1) * 2)};
		}
	}
	if (cur_k < n - 2) {
		string res(100, '0');
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				for (int x = 0; x < 3; x++) {
					for (int y = 0; y < 3; y++) {
						int ni = nxt_off[cur_i][cur_j].first + i - cur_off[cur_i + x][cur_j + y].first;
						int nj = nxt_off[cur_i][cur_j].second + j - cur_off[cur_i + x][cur_j + y].second;
						if (0 <= ni && ni < 10 && 0 <= nj && nj < 10) {
							res[i * 10 + j] = a[x][y][ni * 10 + nj];
						}
					}
				}
			}
		}
		return res;
	}
	if (cur_k == n - 2) {
		if (cur_i % 2 == 1 || cur_j % 2 == 1) {
			return string(100, '0');
		}
		vector<vector<char>> corner(n + 1);
		for (int i = 0; i < n + 1; i++) {
			corner[i].resize(n + 1);
		}
		for (int x = 0; x < 3; x++) {
			for (int y = 0; y < 3; y++) {
				int lx = cur_off[cur_i + x][cur_j + y].first;
				int rx = cur_off[cur_i + x + 1][cur_j + y].first;
				int ly = cur_off[cur_i + x][cur_j + y].second;
				int ry = cur_off[cur_i + x][cur_j + y + 1].second;
				for (int i = lx; i < rx; i++) {
					for (int j = ly; j < ry; j++) {
						int ni = i - cur_off[cur_i][cur_j].first;
						int nj = j - cur_off[cur_i][cur_j].second;
						if (0 <= ni && ni < n + 1 && 0 <= nj && nj < n + 1) {
							corner[ni][nj] = a[x][y][(i - lx) * 10 + (j - ly)];
						}
					}
				}
			}
		}
		int border_row = (cur_i == 0 ? n : 0);
		int border_col = (cur_j == 0 ? n : 0);
		vector<pair<int, int>> border;
		string res3;
		for (int i = 0; i < n + 1; i++) {
			if (cur_i == cur_j) {
				for (int j = n; j >= 0; j--) {
					if (i == border_row || j == border_col) {
						border.push_back({i, j});
						res3 += corner[i][j];
					}
				}
			}
			else {
				for (int j = 0; j < n + 1; j++) {
					if (i == border_row || j == border_col) {
						border.push_back({i, j});
						res3 += corner[i][j];
					}
				}
			}
		}
		res3.resize(41, '0');
		const vector<int> dx = {1, -1, 0, 0};
		const vector<int> dy = {0, 0, 1, -1};
		vector<vector<int>> flag(n + 1);
		for (int i = 0; i < n + 1; i++) {
			flag[i].resize(n + 1);
		}
		int color = 0;
		int cnt = 0;
		for (int i = 0; i < n + 1; i++) {
			for (int j = 0; j < n + 1; j++) {
				if (!flag[i][j] && corner[i][j] == '1') {
					color++;
					flag[i][j] = color;
					bool on_border = false;
					deque<pair<int, int>> q = {{i, j}};
					while (!q.empty()) {
						int cx = q.front().first;
						int cy = q.front().second;
						if (cx == border_row || cy == border_col) {
							on_border = true;
						}
						q.pop_front();
						for (int k = 0; k < 4; k++) {
							int nx = cx + dx[k];
							int ny = cy + dy[k];
							if (0 <= nx && nx < n + 1 && 0 <= ny && ny < n + 1 && corner[nx][ny] == '1' && !flag[nx][ny]) {
								flag[nx][ny] = color;
								q.push_back({nx, ny});
							}
						}
					}
					if (!on_border) {
						cnt++;
					}
				}
			}
		}
		string res4;
		while (cnt) {
			res4 += (char)('0' + (cnt & 1));
			cnt >>= 1;
		}
		res4.resize(17, '0');
		vector<bool> open(n * 2 + 1);
		vector<bool> close(n * 2 + 1);
		string res1;
		string res2;
		for (int i = 0; i < n * 2 + 1; i++) {
			int cx = border[i].first;
			int cy = border[i].second;
			if (corner[cx][cy] == '0') {
				continue;
			}
			if (i > 0 && corner[border[i - 1].first][border[i - 1].second] == '1') {
				continue;
			}
			bool same = true;
			for (int j = i + 1; j < n * 2 + 1; j++) {
				int nx = border[j].first;
				int ny = border[j].second;
				same &= (corner[nx][ny] == '1');
				if (!same && flag[cx][cy] == flag[nx][ny]) {
					open[i] = true;
					close[j] = true;
				}
			}
			res1 += (char)('0' + open[i]);
			res2 += (char)('0' + close[i]);
		}
		res1.resize(21, '0');
		res2.resize(21, '0');
		return res1 + res2 + res3 + res4;
	}
	if (cur_k == n - 1) {
		vector<vector<char>> grid(n * 2 + 1);
		vector<vector<vector<pair<int, int>>>> adj(n * 2 + 1);
		for (int i = 0; i < n * 2 + 1; i++) {
			grid[i].resize(n * 2 + 1, '0');
			adj[i].resize(n * 2 + 1);
		}
		int cnt = 0;
		for (int x = 0; x < 2; x++) {
			for (int y = 0; y < 2; y++) {
				int off_x = x * n;
				int off_y = y * n;
				string res1 = a[x * 2][y * 2].substr(0, 21);
				string res2 = a[x * 2][y * 2].substr(21, 21);
				string res3 = a[x * 2][y * 2].substr(42, 41);
				string res4 = a[x * 2][y * 2].substr(83, 17);
				int border_row = (x == 0 ? n : 0);
				int border_col = (y == 0 ? n : 0);
				vector<pair<int, int>> border;
				for (int i = 0; i < n + 1; i++) {
					if (x == y) {
						for (int j = n; j >= 0; j--) {
							if (i == border_row || j == border_col) {
								border.push_back({i, j});
							}
						}
					}
					else {
						for (int j = 0; j < n + 1; j++) {
							if (i == border_row || j == border_col) {
								border.push_back({i, j});
							}
						}
					}
				}
				vector<pair<int, int>> open;
				int pt = -1;
				for (int i = 0; i < n * 2 + 1; i++) {
					int cx = border[i].first;
					int cy = border[i].second;
					grid[off_x + cx][off_y + cy] = res3[i];
					if (res3[i] == '0') {
						continue;
					}
					if (i > 0 && res3[i - 1] == '1') {
						continue;
					}
					pt++;
					if (res1[pt] == '1') {
						open.push_back({cx, cy});
					}
					if (res2[pt] == '1') {
						int nx = open.back().first;
						int ny = open.back().second;
						open.pop_back();
						adj[off_x + cx][off_y + cy].push_back({off_x + nx, off_y + ny});
						adj[off_x + nx][off_y + ny].push_back({off_x + cx, off_y + cy});
					}
				}
				for (int i = 0; i < 17; i++) {
					cnt += ((res4[i] - '0') << i);
				}
			}
		}
		vector<vector<bool>> flag(n * 2 + 1);
		for (int i = 0; i < n * 2 + 1; i++) {
			flag[i].resize(n * 2 + 1);
		}
		const vector<int> dx = {1, -1, 0, 0};
		const vector<int> dy = {0, 0, 1, -1};
		for (int i = 0; i < n * 2 + 1; i++) {
			for (int j = 0; j < n * 2 + 1; j++) {
				if (!flag[i][j] && grid[i][j] == '1') {
					flag[i][j] = true;
					deque<pair<int, int>> q = {{i, j}};
					cnt++;
					while (!q.empty()) {
						int cx = q.front().first;
						int cy = q.front().second;
						q.pop_front();
						for (auto p: adj[cx][cy]) {
							int nx = p.first;
							int ny = p.second;
							if (0 <= nx && nx < n * 2 + 1 && 0 <= ny && ny < n * 2 + 1 && grid[nx][ny] == '1' && !flag[nx][ny]) {
								flag[nx][ny] = true;
								q.push_back({nx, ny});
							}
						}
						for (int k = 0; k < 4; k++) {
							int nx = cx + dx[k];
							int ny = cy + dy[k];
							if (0 <= nx && nx < n * 2 + 1 && 0 <= ny && ny < n * 2 + 1 && grid[nx][ny] == '1' && !flag[nx][ny]) {
								flag[nx][ny] = true;
								q.push_back({nx, ny});
							}
						}
					}
				}
			}
		}
		string res;
		while (cnt) {
			res += (char)('0' + (cnt & 1));
			cnt >>= 1;
		}
		res.resize(100, '0');
		return res;
	}
	return string(100, '0');
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2032 KB Output is correct
2 Correct 8 ms 2088 KB Output is correct
3 Correct 8 ms 2032 KB Output is correct
4 Correct 8 ms 1976 KB Output is correct
5 Correct 8 ms 2224 KB Output is correct
6 Correct 8 ms 2184 KB Output is correct
7 Incorrect 2 ms 200 KB Incorrect
8 Halted 0 ms 0 KB -