Cod sursă (job #542701)

#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cstring>

using namespace std;

int n, x, y, rx, ry, t[1000 * 1000];

int dx[] = {0, 1, 0, - 1, 1, - 1};

int dy[] = {1, 0, - 1, 0, - 1, 1};
char a[1000][1000];
bool art[4][1000 * 1000];

int fix (int x)
{
    if (t[x] == 0)
        return x;
    return t[x] = fix(t[x]);
}

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

    fin>>n;

    for (int i = 1; i <= n * n; ++ i)
    {
        fin >> x >> y;
        rx = fix (x * (n + 1) + y);
        if (x == 1) art[0][rx] = 1;
        if (x == n) art[1][rx] = 1;
        if (y == 1) art[2][rx] = 1;
        if (y == n) art[3][rx] = 1;
        a[x][y] = (i % 2) + 'a';
        for (int j = 0; j < 6; ++j)
            if (a[x + dx[j]][y + dy[j]] == a[x][y])
            {
                ry = fix((x + dx[j]) * (n + 1) + y + dy[j]);
                if (rx != ry)
                {
                    t[ry] = rx;
                    for (int l = 0; l < 4; ++ l)
                        if (art[l][ry]) 
                            art[l][rx] = 1;
                        else 
                            if (art[l][rx])
                                art[l][ry] = 1;
                }
            }
        if ((i % 2 == 0 && art[0][rx] && art[1][rx]) || (i % 2 && art[2][rx] && art[3][rx]))
        {
            fout<<i;
            return 0;
        }
    }
}