Cod sursă (job #542225)

#include <bits/stdc++.h>

using namespace std;

const int dl[] = { -1, -1, 0, 0, 1, 1 };
const int dc[] = { 0, 1, -1, 1, -1, 0 };

const int Nmax = 500;

int tata[2][Nmax * Nmax + 1];
char aux[2][Nmax * Nmax + 1];
char apart[Nmax + 1][Nmax + 1];

int N, NN;

int cauta( int player, int x )
{
    if ( x != tata[player][x] )
        return tata[player][x] = cauta( player, tata[player][x] );
}

int check( int player, int x, int y )
{
    if ( rand() % 2 == 0 )
        tata[player][x] = y;
    else
        tata[player][y] = x;
    aux[player][x] |= aux[player][y];
    aux[player][y] |= aux[player][x];
    return ( aux[player][x] == 3 );
}

void init()
{
    memset( aux, 0, sizeof( aux ) );
    memset( apart, 0, sizeof( apart ) );
    for ( int i = 1; i <= N * N; ++i )
        tata[0][i] = tata[1][i] = i;

    for ( int i = 1; i <= N; ++i )
    {
        aux[1][ ( i - 1 ) * N + 1 ] = 1;
        aux[1][ ( i - 1 ) * N + N ] = 2;
    }
    for ( int i = 1; i <= N; ++i )
    {
        aux[0][i] = 1;
        aux[0][ ( N - 1 ) * N + i ] = 2;
    }
}

int valid( int player, int x, int y )
{
    return ( 1 <= x && x <= N && 1 <= y && y <= N && apart[x][y] == player + 1 );
}

int main()
{
    ifstream cin("hex.in");
    ofstream cout("hex.out");
    cin >> N;
    init();
    for ( int i = 1; i <= N * N; ++i )
    {
        int a, b;
        cin >> a >> b;
        apart[a][b] = ( i & 1 ) + 1;
        int stop = 0;
        for ( int k = 0; k < 6; ++k )
        {
            int x = a + dl[k];
            int y = b + dc[k];
            if ( valid( ( i & 1 ), x, y ) )
            {
                int fx = cauta( i & 1, N * ( x - 1 ) + y );
                int fy = cauta( i & 1, N * ( a - 1 ) + b );
                if ( fx != fy )
                {
                    stop |= check( i & 1, fx, fy );
                }
            }
        }
        if ( stop )
        {
            cout << i << "\n";
            i = N * N + 1;
        }
    }
    return 0;
}