#include "mars.h"
#include <bits/stdc++.h>
std::pair<int, int> get_bounds(int i, int k, int n) {
int left = i * (2 * n + 1) / (2 * (n - k) + 1);
int right = (i + 1) * (2 * n + 1) / (2 * (n - k) + 1);
return {left, right};
}
std::string solve(std::vector<std::string> g) {
int n = g.size();
std::vector<int> used(n * n);
auto id = [&](int x, int y) {
return x * n + y;
};
auto dfs = [&](auto self, int x, int y) -> void {
used[id(x, y)] = 1;
if (x - 1 >= 0) {
if (!used[id(x - 1, y)] && g[x - 1][y] == '1') {
self(self, x - 1, y);
}
}
if (x + 1 < n) {
if (!used[id(x + 1, y)] && g[x + 1][y] == '1') {
self(self, x + 1, y);
}
}
if (y - 1 >= 0) {
if (!used[id(x, y - 1)] && g[x][y - 1] == '1') {
self(self, x, y - 1);
}
}
if (y + 1 < n) {
if (!used[id(x, y + 1)] && g[x][y + 1] == '1') {
self(self, x, y + 1);
}
}
};
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (!used[i * n + j] && g[i][j] == '1') {
dfs(dfs, i, j);
ans++;
}
}
}
std::string res;
while (ans) {
res.push_back((ans & 1) + '0');
ans >>= 1;
}
while (res.size() < 100) {
res.push_back('0');
}
return res;
}
std::string process(std::vector<std::vector<std::string>> a, int xx, int yy, int k, int n) {
std::vector<std::string> g(2 * n + 1, std::string(2 * n + 1, '0'));
auto regen = [&](std::string s, int x, int y) {
auto [lx, rx] = get_bounds(x, k, n);
auto [ly, ry] = get_bounds(y, k, n);
for (int i = lx; i < rx; i++) {
for (int j = ly; j < ry; j++) {
int u = i - lx;
int v = j - ly;
g[i][j] = s[u * (ry - ly) + v];
}
}
};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
regen(a[i][j], xx + i, yy + j);
}
}
if (k == n - 1) {
return solve(g);
}
auto [lx, rx] = get_bounds(xx, k + 1, n);
auto [ly, ry] = get_bounds(yy, k + 1, n);
std::string res(100, '0');
for (int i = lx; i < rx; i++) {
for (int j = ly; j < ry; j++) {
int u = i - lx;
int v = j - ly;
res[u * (ry - ly) + v] = g[i][j];
}
}
return res;
}
