1450C1 - Errich Tac Toe
06 Dec 2020 — Tags: constructive_algorithm,coloring_argument — URLEditorial. Hint: Use the Pigeonhole Principle to prove that:
\[\min{x_0, x_1, x_2} \leq floor(\frac{k}{3})\]Time complexity: $O(n^2)$
Memory complexity: $O(n^2)$
Click to show code.
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(), k = 0;
array<vector<ii>, 3> cnt;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
if (board[i][j] == 'X')
{
cnt[(i + j) % 3].emplace_back(i, j);
++k;
}
}
}
for (auto &v : cnt)
{
if ((int)(v).size() <= k / 3)
{
for (auto [i, j] : v)
board[i][j] = 'O';
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;
}