Cod sursă (job #353988)

#include <fstream>
#include <vector>

using namespace std;

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

int Compress(const Pair &p, int len)
{
  return p.first * len + p.second;
}

Pair Decompress(int comp, int len)
{
  return {comp / len, comp % len};
}

int ExpandBounds(int comp_a, int comp_b, int len)
{
  auto bounds_a = Decompress(comp_a, len);
  auto bounds_b = Decompress(comp_b, len);

  auto small = min(bounds_a.first, bounds_b.first);
  auto big = max(bounds_a.second, bounds_b.second);

  return Compress({small, big}, len);
};

class DSet
{
public:
  DSet(int rows, int cols)
    : fathers_(vector<int>(rows * cols, -1)),
      bounds_(vector<int>(rows * cols, -1)),
      cols_(cols) {}

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

  void SetBounds(const Position &p, int small, int big);

  Pair GroupBounds(const Position &p);

private:
  int Root(int node);

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

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

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

void DSet::SetBounds(const Position &p, int small, int big)
{
  auto index = Compress(p, cols_);
  if (bounds_[index] == -1) {
    bounds_[index] = Compress({small, big}, cols_);
  }
}

Pair DSet::GroupBounds(const Position &p)
{
  auto index = Compress(p, cols_);
  auto comp = bounds_[Root(index)];
  return Decompress(comp, 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 SetInitBounds(DSet &dset, int x, int y, int col)
{
  auto bound = (col == 0 ? y : x);
  dset.SetBounds({x, y}, bound, bound);
}

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;
  SetInitBounds(dset, 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) {
      SetInitBounds(dset, 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 small = 0;
  auto big = (int)(mat[x][y] == 0 ? mat.size() : mat[0].size()) - 1;

  return bounds.first == small && bounds.second == big;
}

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 (i + 1 < 2 * n) {
      continue;
    }

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