1450C2 - Errich Tac Toe

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
void solve(vector<string> &board)
{
    int n = (int)(board).size(), kx = 0, ko = 0;
    array<vector<ii>, 3> cntx, cnto;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (board[i][j] == 'X')
            {
                cntx[(i + j) % 3].emplace_back(i, j);
                ++kx;
            }
            if (board[i][j] == 'O')
            {
                cnto[(i + j) % 3].emplace_back(i, j);
                ++ko;
            }
        }
    }
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            if (i == j)
                continue;
            if ((int)(cntx[i]).size() + (int)(cnto[j]).size() <= (kx + ko) / 3)
            {
                for (auto [r, c] : cntx[i])
                    board[r][c] = 'O';
                for (auto [r, c] : cnto[j])
                    board[r][c] = 'X';
                return;
            }
        }
    }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<string> board(n);
        read_n(begin(board), n);
        solve(board);
        write(begin(board), end(board));
    }
    return 0;
}