Cod sursă (job #353968)

#include <fstream>
#include <vector>

using namespace std;

typedef pair<int, int> Position;
typedef vector<vector<int>> Matrix;

int Index(const Position &pos, int cols)
{
  return pos.first * cols + pos.second;
}

Position Pos(int index, int cols)
{
  return {index / cols, index % cols};
}

struct Bounds
{
  int top_left;
  int bot_right;
};

Bounds Expand(const Bounds &a, const Bounds &b, int cols)
{
  auto top_left_a = Pos(a.top_left, cols);
  auto top_left_b = Pos(b.top_left, cols);

  auto bot_right_a = Pos(a.bot_right, cols);
  auto bot_right_b = Pos(b.bot_right, cols);

  auto top = min(top_left_a.first, top_left_b.first);
  auto left = min(top_left_a.second, top_left_b.second);

  auto bot = max(bot_right_a.first, bot_right_b.first);
  auto right = max(bot_right_a.second, bot_right_b.second);

  return {Index({top, left}, cols), Index({bot, right}, cols)};
};


class DSet
{
public:
  DSet(int rows, int cols)
    : fathers_(vector<int>(rows * cols, -1)),
      cols_(cols)
  {
    bounds_.resize(rows * cols);
    for (int i = 0; i < rows; ++i) {
      for (int j = 0; j < cols; ++j) {
        auto ind = Index({i, j}, cols);
        bounds_[ind] = {ind, ind};
      }
    }
  }

  void Unite(const Position &a, const Position &b);

  Bounds GroupBounds(const Position &p);

private:
  int Root(int node);

  vector<int> fathers_;
  vector<Bounds> bounds_;
  int cols_;
};

void DSet::Unite(const Position &a, const Position &b)
{
  auto ra = Root(Index(a, cols_));
  auto rb = Root(Index(b, cols_));

  if (ra != rb) {
    fathers_[rb] = ra;
    bounds_[ra] = Expand(bounds_[ra], bounds_[rb], cols_);
  }
}

Bounds DSet::GroupBounds(const Position &p)
{
  return bounds_[Root(Index(p, cols_))];
}

int DSet::Root(int node)
{
  if (fathers_[node] == -1) {
    return node;
  }
  return fathers_[node] = Root(fathers_[node]);
}

bool InBounds(const Matrix &mat, int x, int y)
{
  return x >= 0 && x < (int)mat.size() &&
         y >= 0 && y < (int)mat[0].size();
}

void PlaceToken(Matrix &mat, DSet &dset, int x, int y, int col)
{
  static const vector<Position> kMods = {
    {-1, 0}, {-1, 1}, {0, 1}, {1, 0}, {1, -1}, {0, -1}
  };

  mat[x][y] = col;

  for (const auto &mod : kMods) {
    auto cx = x + mod.first;
    auto cy = y + mod.second;

    if (InBounds(mat, cx, cy) && mat[cx][cy] == col) {
      dset.Unite({cx, cy}, {x, y});
    }
  }
}

bool IsWinningMove(const Matrix &mat, DSet &dset, int x, int y)
{
  auto bounds = dset.GroupBounds({x, y});
  auto top_left = Pos(bounds.top_left, mat[0].size());
  auto bot_right = Pos(bounds.bot_right, mat[0].size());

  auto rows = (int)mat.size();
  auto cols = (int)mat[0].size();

  if (mat[x][y] == 0) {
    return top_left.second == 0 && bot_right.second == cols - 1;
  } else {
    return top_left.first == 0 && bot_right.first == rows - 1;
  }
}

int main()
{
  ifstream fin("hex.in");
  ofstream fout("hex.out");

  int n;
  fin >> n;

  Matrix mat(n, vector<int>(n, -1));
  DSet dset(n, n);

  for (int i = 0; i < n * n; ++i) {
    int col = i % 2;
    int x, y;

    fin >> x >> y;
    x -= 1;
    y -= 1;

    PlaceToken(mat, dset, x, y, col);

    if (IsWinningMove(mat, dset, x, y)) {
      fout << i + 1 << "\n";
      break;
    }
  }
  return 0;
}