#include "Azzurro.h"
std::vector<std::vector<int>> Azzurro(int N, int L, std::string S) {
int Lmax = 51;
std::vector<int> s(Lmax, 0);
std::vector<std::vector<int>> res(N, std::vector<int>(N, 0));
std::vector<std::vector<std::pair<int, int>>> pos(2 * N - 1);
std::vector<std::vector<int>> pos2(N, std::vector<int>(N, 0));
for(int i = 0; i < L; i++){
if(S[i] == 'A') s[i] = 0;
else s[i] = 1;
}
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pos2[i][j] = pos[i + j].size();
pos[i + j].emplace_back(i, j);
}
}
res[0][0] = s[0];
res[N - 1][N - 1] = s[Lmax - 1];
int idx = 1;
for(int k = 1; k < 2 * N - 2; k++){
int xr = 0;
for(int l = 1; l < pos[k].size(); l++){
auto [i, j] = pos[k][l];
res[i][j] = s[idx];
idx++;
if(l % 2 == 0){
xr ^= res[i][j];
}
}
auto [i, j] = pos[k][0];
res[i][j] = xr;
}
return res;
}
#include "Bordeaux.h"
#include <iostream>
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T) {
std::vector<int> res;
std::vector<std::vector<std::pair<int, int>>> pos(2 * N - 1);
std::vector<std::vector<int>> pos2(N, std::vector<int>(N, 0));
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
pos2[i][j] = pos[i + j].size();
pos[i + j].emplace_back(i, j);
}
}
int x = 0, y = 0;
for(int k = 0; k < 2 * N - 1; k++){
if(k == 0 || k == 2 * N - 2){
auto [i, j] = pos[k][0];
res.emplace_back(1 ^ T[i][j]);
continue;
}
int tar = 1;
for(int l = 0; l < pos[k].size(); l++){
if(l % 2 == 0){
auto [i, j] = pos[k][l];
tar ^= T[i][j];
}
}
int nx = x, ny = y + 1;
if(x + 1 < N && pos2[x + 1][y] % 2 == tar){
nx = x + 1;
ny = y;
}
T[nx][ny] ^= 1;
for(int l = 1; l < pos[k].size(); l++){
auto [i, j] = pos[k][l];
res.emplace_back(T[i][j]);
}
x = nx;
y = ny;
}
std::string s = "";
for(int i = 0; i < L; i++){
if(res[i] == 0) s += 'A';
else s += 'B';
}
return s;
}
