#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct dsu {
vector<int> p;
vector<int> size;
dsu(int N) {
p.resize(N);
iota(p.begin(), p.end(), 1);
size.assign(N, 1);
}
int boss(int u) {
if (p[u] == u) return u;
return p[u] = boss(p[u]);
}
void merge(int a, int b) {
a = boss(a);
b = boss(b);
if (size[a] < size[b]) swap(a, b);
size[a] += size[b];
p[b] = a;
}
};
int get_islands(string s) {
// negli ultimi 9 bit mi salvo il numero di componenti.
// Sto considerando le componenti sotto (o sopra) la diagonale, che ha come upperbound
// (2N + 1)(2N + 1) / 4 = 420, nel caso della scacchiera. Questo numero sta in 9 bit perché è minore di 2^9 = 512.
int islands = 0;
for (int i = 0; i < 9; i ++) {
if (s[100 - 1 - i] == '1') islands += (1 << i);
}
return islands;
}
vector<int> decode_components(string s) {
// In 91 bit mi salvo le componenti dei quadratini sulla diagonale.
// Le componenti formano una sorta di stringa di parentesi:
// questo perché tutti i nodi stanno su una linea, le connessioni si trovano su un semipiano e il grafo è planare.
// Quindi ogni quadratino può essere scritto come uno tra questi simboli:
// o : 0 il quadratino è acqua
// (. : 1
// . : 2
// .) : 3
// (.) : 4
// Essendo 5 simboli, per comprimerli bene, invece di tenermi 3 bits per ognuno, prendo
// 3 simboli consecutivi, li converto in base 5 e poi li converto in binario.
// Questo mi fa usare 7 bit per 3 quadratini invece di 9.
// Dato che la lunghezza più lunga della diagonale che mi interessa è (2N + 1 - 2) = 39.
// Quindi mi bastano 39 * 7 / 3 = 91 bits per salvarmi le componenti sulla diagonale.
vector<int> parenthesis;
for (int b = 0; b < 91; b += 7) {
// converto 7 bits in un numero
int num = 0;
for (int i = 0; i < 7; i ++) {
if (s[b + i] == '1') num += (1 << i);
}
// converto questo numero in base 5 (di 3 cifre)
vector<int> num_base_5;
for (int c = 0; c < 3; c ++) {
num_base_5.push_back(num % 5);
num /= 5;
}
// ogni numero in base 5 corrisponde a uno dei 5 simboli della stringa di parentesi
for (auto x : num_base_5) parenthesis.push_back(x);
}
vector<int> comps;
int next_comp = 2; // inizio con 2 così lascio da parte gli 0 (vuoti) e gli 1 (ancora senza comps)
stack<int> curr_comp;
for (auto x : parenthesis) {
if (x == 0) { // o
comps.push_back(0);
}
if (x == 1) { // (.
curr_comp.push(next_comp);
next_comp ++;
comps.push_back(curr_comp.top());
}
if (x == 2) { // .
comps.push_back(curr_comp.top());
}
if (x == 3) { // .)
comps.push_back(curr_comp.top());
curr_comp.pop();
}
if (x == 4) { // (.)
curr_comp.push(next_comp);
next_comp ++;
comps.push_back(curr_comp.top());
curr_comp.pop();
}
}
return comps;
}
string encode_components(vector<int> comps, int islands) {
// mi salvo l'inizio e la fine di ogni gruppo per capire come vanno le parentesi
map<int, int> inizio;
map<int, int> fine;
for (int i = 0; i < comps.size(); i ++) {
if (comps[i] == 0) continue;
if (!inizio.count(comps[i])) inizio[comps[i]] = i;
fine[comps[i]] = max(fine[comps[i]], i);
}
// scrivo le parentesi
vector<int> parenthesis(39, 0);
for (int i = 0; i < comps.size(); i ++) {
if (comps[i] == 0) { // o
parenthesis[i] = 0;
}
if (inizio[comps[i]] == i && fine[comps[i]] == i) { // (.
parenthesis[i] = 1;
}
if (inizio[comps[i]] != i && fine[comps[i]] != i) { // .
parenthesis[i] = 2;
}
if (inizio[comps[i]] != i && fine[comps[i]] == i) { // .)
parenthesis[i] = 3;
}
if (inizio[comps[i]] == i && fine[comps[i]] == i) { // (.)
parenthesis[i] = 4;
}
}
string s;
// alla fine del ciclo s sarà lunga 91 caratteri
for (int p = 0; p < 39; p += 3) {
// trasformo una sequenza contigua di tre simboli in un numero in base 5
int num = 0;
for (int c = 0; c < 3; c ++) {
num *= 5;
num += parenthesis[p + c];
}
// ricopio il numero in binario su una substring lunga 7 in s
for (int i = 0; i < 7; i ++) {
if ((1 << i) & num) s.push_back('1');
else s.push_back('0');
}
}
// codifico il numero di isole negli ultimi 9 bit di s.
for (int i = 0; i < 9; i ++) s.push_back('0');
for (int i = 0; i < 9; i ++) {
if ((1 << i) & islands) s[100 - 1 - i] = '1';
}
return s;
}
void calc_comps(vector<vector<int>> &grid, int islands, int diag, int N) {
// esplicita le varie componenti dei quadratini non sulla diagonale
int comps_num = 2;
for (int i = 0; i < 2 * N + 1 && i - diag < 2 * N + 1; i ++) {
int j = i - diag;
comps_num = max(comps_num, grid[i][j]);
}
comps_num ++;
for (int i = 0; i < 2 * N; i ++) {
for (int j = 0; j < 2 * N; j ++) {
// ignora gli elementi sulla diagonale
if (i - j == diag) continue;
if (grid[i][j]) {
grid[i][j] = comps_num;
comps_num ++;
}
}
}
dsu comps(comps_num + 3); // + epsilon per essere sicuro
for (int i = 0; i < 2 * N - 1; i ++) {
for (int j = 0; j < 2 * N; j ++) {
if (grid[i][j] && grid[i + 1][j]) {
comps.merge(grid[i][j], grid[i + 1][j]);
}
}
}
for (int i = 0; i < 2 * N; i ++) {
for (int j = 0; j < 2 * N - 1; j ++) {
if (grid[i][j] && grid[i][j + 1]) {
comps.merge(grid[i][j], grid[i][j + 1]);
}
}
}
for (int i = 0; i < 2 * N; i ++) {
for (int j = 0; j < 2 * N; j ++) {
grid[i][j] = comps.boss(grid[i][j]);
}
}
}
string process(vector<vector<string>> a, int i, int j, int k, int N) {
int m = 2 * (N - k - 1);
if (i != m && j != m) {
// non è sul bordo quindi lo lascio uguale
return a[0][0];
}
if (k == N - 1) {
vector<vector<int>> grid(2 * N + 1, vector<int>(2 * N + 1));
for (int y = 0; y < 2; y ++) {
for (int x = 0; x < 2; x ++) {
grid[y][x] = (a[y][x][0] == '1') ? 1 : 0;
}
}
for (int b = 0; 2 + b < 2 * N + 1; b ++) {
grid[b + 2][b + 2] = (a[2][2][b] == '1') ? 1 : 0;
}
int islands = get_islands(a[2][0]) + get_islands(a[0][2]);
vector<int> diag_sotto = decode_components(a[2][0]);
// la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0
for (int b = 0; b < diag_sotto.size() && 2 + b < 2 * N + 1; b ++) {
grid[2 + b][b] = diag_sotto[b];
}
vector<int> diag_sopra = decode_components(a[0][2]);
// la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0
for (int b = 0; b < diag_sopra.size() && 2 + b < 2 * N + 1; b ++) {
grid[b][2 + b] = diag_sopra[b];
}
calc_comps(grid, islands, i - j, N);
set<int> visited_comps;
for (int i = 0; i < 2 * N; i ++) {
for (int j = 0; j < 2 * N; j ++) {
if (grid[i][j] == 0) continue;
if (visited_comps.count(grid[i][j])) continue;
islands ++;
visited_comps.insert(grid[i][j]);
}
}
// scrivo il numero di isole in binario nel risultato
string s;
for (int i = 0; i < 100; i ++) s.push_back('0');
for (int p = 0; p < 20; p ++) {
if ((1 << p) & islands) s[p] = '1';
}
return s;
}
if (j == 0) {
// mi salvo le componenti nel triangolo in basso a sinistra
vector<vector<int>> grid(2 * N + 1, vector<int>(2 * N + 1));
// y < 2 ricopio i singoli punti
for (int y = 0; y < 2; y ++) {
for (int x = 0; x < 3; x ++) {
grid[i + y][j + x] = (a[y][x][0] == '1') ? 1 : 0;
}
}
// y = 2, x > 1 devo ricopiare le diagonali sotto
for (int x = 1; x < 3; x ++) {
for (int b = 0; i + 2 + b < 2 * N + 1; b ++) {
grid[i + 2 + b][x + b] = (a[2][x][b] == '1') ? 1 : 0;
}
}
int islands = get_islands(a[2][0]);
if (k != 0) {
vector<int> diag_sotto = decode_components(a[2][0]);
// la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0
for (int b = 0; b < diag_sotto.size() && i + 2 + b < 2 * N + 1; b ++) {
grid[i + 2 + b][b] = diag_sotto[b];
}
}
else {
// prima iterazione : inserisco il quadratino così com'è
grid[i + 2][j] = a[2][0][0];
}
// calcola le componenti connesse.
calc_comps(grid, islands, i - j, N);
// e aggiorna le componenti
vector<int> new_diag_sotto(2 * N + 1);
for (int b = 0; i + 2 + b < 2 * N + 1; b ++) new_diag_sotto[i] = grid[i + 2 + b][b];
set<int> visited_comps;
for (auto x : new_diag_sotto) {
if (x != 0) visited_comps.insert(x);
}
for (int i = 0; i < 2 * N; i ++) {
for (int j = 0; j < 2 * N; j ++) {
if (grid[i][j] == 0) continue;
if (visited_comps.count(grid[i][j])) continue;
islands ++;
visited_comps.insert(grid[i][j]);
}
}
string res = encode_components(new_diag_sotto, islands);
return res;
}
if (i == 0) {
// mi salvo le componenti nel triangolo in alto a destra.
// il codice è analogo a quello sopra
vector<vector<int>> grid(2 * N + 1, vector<int>(2 * N + 1));
// x < 2 ricopio i singoli punti
for (int x = 0; x < 2; x ++) {
for (int y = 0; y < 3; y ++) {
grid[i + y][j + x] = (a[y][x][0] == '1') ? 1 : 0;
}
}
// x = 2, y > 1 devo ricopiare le diagonali sotto
for (int y = 1; y < 3; y ++) {
for (int b = 0; j + 2 + b < 2 * N + 1; b ++) {
grid[y + b][j + 2 + b] = (a[y][2][b] == '1') ? 1 : 0;
}
}
int islands = get_islands(a[0][2]);
if (k != 0) {
vector<int> diag_sopra = decode_components(a[0][2]);
// la condizione (b < diag_sotto.size()) è inutile perché ha sempre 2 * N - 1 elementi, e quelli in eccesso sono segnati come 0
for (int b = 0; b < diag_sopra.size() && j + 2 + b < 2 * N + 1; b ++) {
grid[b][j + 2 + b] = diag_sopra[b];
}
}
else {
// prima iterazione : inserisco il quadratino così com'è
grid[i][j + 2] = a[0][2][0];
}
// calcola le componenti connesse.
calc_comps(grid, islands, i - j, N);
// e aggiorna le componenti
vector<int> new_diag_sopra(2 * N + 1);
for (int b = 0; i + 2 + b < 2 * N + 1; b ++) new_diag_sopra[i] = grid[i + 2 + b][b];
set<int> visited_comps;
for (auto x : new_diag_sopra) {
if (x != 0) visited_comps.insert(x);
}
for (int i = 0; i < 2 * N; i ++) {
for (int j = 0; j < 2 * N; j ++) {
if (grid[i][j] == 0) continue;
if (visited_comps.count(grid[i][j])) continue;
islands ++;
visited_comps.insert(grid[i][j]);
}
}
string res = encode_components(new_diag_sopra, islands);
return res;
}
// se è sui bordi però non è il triangolo (ne o so) allora semplicemente mi salvo la diagonale
// parte dal primo carattere e poi scende piano piano in basso a destra
string diagonal = a[0][0]; // comincia copiando il primo punto (e anche il resto vuoto, così è lungo 100)
diagonal[1] = a[1][1][0]; // copio il secondo punto
for (int b = 0; b + 2 < 100; b ++) {
diagonal[b + 2] = a[2][2][b]; // ricopio la diagonale salvata in a[2][2], che era il bordo precedente.
}
// // max è 2n, max m è 2n - 2
// the diagonal is (2n + 1 - m) bits long
return diagonal;
}
