#include "mars.h"
#include <numeric>
#include <iostream>
#include <map>
using namespace std;
using pi = pair<int, int>;
struct Dsu {
vector<int> p, c;
Dsu (int n) : p(n), c(n, 1) {
iota(p.begin(), p.end(), 0);
}
int root(int v) {
return v == p[v] ? v : p[v] = root(p[v]);
}
bool unite(int a, int b) {
a = root(a), b = root(b);
if (a == b) {
return false;
} else {
if (c[a] < c[b]) swap(a, b);
p[b] = a;
c[a] += c[b];
return true;
}
}
};
vector<int> get_colors(vector<string> v, vector<int> info, int& additional_cost, vector<int>& slice, int& slice_diff) {
const int n = v.size();
Dsu dsu(n*n);
vector<pi> bound;
for (int i = n - 1; i >= 2; --i) bound.emplace_back(i, 2);
for (int i = 3; i < n; ++i) bound.emplace_back(2, i);
vector<int> st_colors;
for (int i = 0; i < bound.size(); ++i) {
auto [x, y] = bound[i];
if (v[x][y] == '1') {
if (info[i]) {
st_colors.push_back(n*x + y);
} else {
dsu.unite(st_colors.back(), n*x+y);
}
} else {
if (info[i]) st_colors.pop_back();
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
if (v[i][j] != '1') continue;
const int s = n*i + j;
if (i + 1 < n && v[i+1][j] == '1') dsu.unite(s, s+n);
if (j + 1 < n && v[i][j+1] == '1') dsu.unite(s, s+1);
}
vector<int> used(n*n);
for (int i = 0; i < n; ++i) {
if (v[0][i] == '1' && !used[dsu.root(i)]) used[dsu.root(i)] = 1, ++slice_diff;
if (v[i][0] == '1' && !used[dsu.root(i*n)]) used[dsu.root(i*n)] = 1, ++slice_diff;
}
for (int i = 1; i < n; ++i)
for (int j = 1; j < n; ++j) {
if (v[i][j] == '0') continue;
int rt = dsu.root(n*i+j);
if (!used[rt]) ++additional_cost;
used[rt] = 1;
}
bound.clear();
for (int i = n - 1; i >= 0; --i) bound.emplace_back(i, 0);
for (int i = 1; i < n; ++i) bound.emplace_back(0, i);
vector<int> res;
for (auto [x, y] : bound) {
res.push_back(dsu.root(n*x+y));
slice.push_back(v[x][y] - '0');
}
return res;
}
void write_cost(string& res, int cost) {
for (int i = 0; i < 11; ++i) {
res[i+1] = (cost >> i) % 2 ? '1' : '0';
}
}
string get_answer(int ans) {
string res(100, '0');
for (int i = 0; i < 20; ++i) {
res[i] = '0' + (ans >> i) % 2;
}
return res;
}
int load_cost(string& res) {
int cost = 0;
for (int i = 0; i < 11; ++i) {
cost += (res[i+1] - '0') << i;
}
return cost;
}
vector<int> get_mask_by_color(vector<int> cols, vector<int> slice) {
const int n = cols.size();
vector<int> res(n+1), st;
for (int i = 0; i < n; ++i) {
if (slice[i] == 0 || cols[i] == -1) continue;
int last = i;
for (int j = i + 1; j < n; ++j) {
if (cols[j] == cols[i]) {
cols[j] = -1;
last = j;
}
}
res[i] = 1;
res[last+1] = 1;
}
return res;
}
string process(vector<vector<string>> a, int i, int j, int k, int n) {
const vector<pi> dpos = { {-1,0}, {1,0}, {0,1}, {0,-1} };
if (max(i, j) != 2 * (n-k-1)) return a[0][0];
string res(100, '0');
const int w = 2 * k + 3;
if (max(i, j) == 2*n-2) {
if (i == j) {
vector<int> info { 1, 1 }, slice;
vector v(3, string(3, '0'));
for (int i = 3; i--; )
for (int j = 3; j--; ) v[i][j] = a[i][j][0];
int cost = 0, slice_diff = 0;
auto cols = get_colors(v, info, cost, slice, slice_diff);
auto info_write = get_mask_by_color(cols, slice);
res[0] = a[0][0][0];
write_cost(res, cost);
for (int i = 0; i < info_write.size(); ++i) res[i+12] = info_write[i] + '0';
if (i == 0) return get_answer(cost + slice_diff);
return res;
} else {
if (i == 2*n-2 && j % 2 == 0) {
res[0] = a[0][0][0];
res[1] = a[1][0][0];
res[2] = a[2][0][0];
res[3] = a[0][1][0];
res[4] = a[1][1][0];
res[5] = a[2][1][0];
return res;
}
if (j == 2*n-2 && i % 2 == 0) {
res[0] = a[0][0][0];
res[1] = a[0][1][0];
res[2] = a[0][2][0];
res[3] = a[1][0][0];
res[4] = a[1][1][0];
res[5] = a[1][2][0];
return res;
}
if (i == 2*n-2 && j == 2*n-3) {
res[0] = a[0][0][0];
res[1] = a[0][1][0];
res[2] = a[1][1][0];
res[3] = a[2][1][0];
return res;
}
if (i == 2*n-3 && j == 2*n-2) {
res[0] = a[0][0][0];
res[1] = a[1][0][0];
res[2] = a[1][1][0];
res[3] = a[1][2][0];
return res;
}
}
} else if (max(i, j) == 2*(n-k)-2) {
if (i == j) {
int cost = load_cost(a[2][2]);
vector v(w, string(w, '0'));
v[0][0] = a[0][0][0];
v[0][1] = a[0][1][0];
v[1][0] = a[1][0][0];
v[1][1] = a[1][1][0];
v[2][2] = a[2][2][0];
const int W = w - 2;
for (int i = 0; i < W; ++i) {
v[i+2][0] = a[2][0][i];
v[i+2][1] = a[2][0][i+W];
v[0][i+2] = a[0][2][i];
v[1][i+2] = a[0][2][i+W];
}
// cerr << a[2][1] << endl;
for (int i = 0; i < W; ++i) {
v[i+2][2] = a[2][1][i+1];
v[2][2+i] = a[1][2][i+1];
}
vector<int> info(2*W), slice;
for (int i = 0; i < 2*W; ++i) info[i] = a[2][2][i+12] - '0';
int slice_cost = 0;
auto cols = get_colors(v, info, cost, slice, slice_cost);
auto info_write = get_mask_by_color(cols, slice);
res[0] = a[0][0][0];
write_cost(res, cost);
for (int i = 0; i < info_write.size(); ++i) res[i+12] = info_write[i] + '0';
if (i == 0) return get_answer(cost + slice_cost);
return res;
} else {
if (i == 2*(n-k)-2 && j % 2 == 0) {
res[0] = a[0][0][0];
res[1] = a[1][0][0];
for (int i = 2; i < w; ++i) {
res[i] = a[2][0][i-2];
}
res[w] = a[0][1][0];
res[w+1] = a[1][1][0];
for (int i = 2; i < w; ++i) {
res[i+w] = a[2][0][i+w-4];
}
return res;
}
if (j == 2*(n-k)-2 && i % 2 == 0) {
res[0] = a[0][0][0];
res[1] = a[0][1][0];
for (int i = 2; i < w; ++i) {
res[i] = a[0][2][i-2];
}
res[w] = a[1][0][0];
res[w+1] = a[1][1][0];
for (int i = 2; i < w; ++i) {
res[i+w] = a[0][2][i+w-4];
}
return res;
}
if (i == 2*(n-k)-2 && j == 2*(n-k)-3) {
res[0] = a[0][0][0];
res[1] = a[0][1][0];
res[2] = a[1][1][0];
for (int i = 0; i < w-2; ++i) {
res[i+3] = a[2][1][i];
}
return res;
}
if (j == 2*(n-k)-2 && i == 2*(n-k)-3) {
res[0] = a[0][0][0];
res[1] = a[1][0][0];
res[2] = a[1][1][0];
for (int i = 0; i < w-2; ++i) {
res[i+3] = a[1][2][i];
}
return res;
}
}
}
return a[0][0];
}
