#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[cx][cy].push_back({nx, ny});
adj[nx][ny].push_back({cx, 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');
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
200 KB |
Incorrect |
| 2 |
Halted |
0 ms |
0 KB |
- |
