Cod sursă (job #641351)

#include <algorithm>
#include <fstream>
#include <vector>
#define MAX 501
using namespace std;

ifstream cin( "hex.in" );
ofstream cout( "hex.out" );

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

struct Andrei {
    int lin, col, val, ind;
};

bool cmp( const Andrei& A, const Andrei& B ) {
    return ( A.val < B.val );
}

struct Andrei007 {
    int minL, maxL;
};

struct point {
    int l, c;
};

Andrei007 buck[ MAX * MAX + 1 ];
int okR[ MAX + 1 ][ MAX + 1 ];
int okB[ MAX + 1 ][ MAX + 1 ];
int dad[ MAX * MAX + 1 ];
int n, m, k, no;
int minL, maxL;

int tata( int ind ) {
    if( dad[ ind ] == ind )
        return ind;
    return dad[ ind ] = tata( dad[ ind ] );
}

bool unesteB( point a, point b ) {
    int tata1 = tata( okB[ a.l ][ a.c ] );
    int tata2 = tata( okB[ b.l ][ b.c ] );
    if( tata1 == tata2 )
        return ( buck[ tata2 ].maxL - buck[ tata2 ].minL + 1 ) == n;
    dad[ tata2 ] = tata1;
    buck[ tata1 ].minL = min( buck[ tata2 ].minL, buck[ tata1 ].minL );
    buck[ tata1 ].maxL = max( buck[ tata2 ].maxL, buck[ tata1 ].maxL );
    return ( buck[ tata1 ].maxL - buck[ tata1 ].minL + 1 ) == n;
}

bool unesteR( point a, point b ) {
    int tata1 = tata( okR[ a.l ][ a.c ] );
    int tata2 = tata( okR[ b.l ][ b.c ] );
    if( tata1 == tata2 )
        return ( buck[ tata2 ].maxL - buck[ tata2 ].minL + 1 ) == n;
    dad[ tata2 ] = tata1;
    buck[ tata1 ].minL = min( buck[ tata2 ].minL, buck[ tata1 ].minL );
    buck[ tata1 ].maxL = max( buck[ tata2 ].maxL, buck[ tata1 ].maxL );
    return ( buck[ tata1 ].maxL - buck[ tata1 ].minL + 1 ) == n;
}

int main()
{
    cin >> n;

    int l, c;
    int k = n * n;
    for( int i = 1; i <= k; i++  ) {
        cin >> l >> c;
        int V = ( l - 1 ) * n + c;
        if( i & 1 ) {
            okR[ l ][ c ] = V;
            dad[ V ] = V;
            buck[ V ].minL = c;
            buck[ V ].maxL = c;
            for( int d = 0; d < 6; d++ )
                if( okR[ l + dl[ d ] ][ c + dc[ d ] ] )
                    if( unesteR( { l, c }, { l + dl[ d ], c + dc[ d ] } ) ) {
                        cout << i << '\n';
                        exit( 0 );
                    }
        } else {
            okB[ l ][ c ] = V;
            dad[ V ] = V;
            buck[ V ].minL = l;
            buck[ V ].maxL = l;
            for( int d = 0; d < 6; d++ )
                if( okB[ l + dl[ d ] ][ c + dc[ d ] ] )
                    if( unesteB( { l, c }, { l + dl[ d ], c + dc[ d ] } ) ) {
                        cout << i << '\n';
                        exit( 0 );
                    }
        }
    }
    cout << k << '\n';
    return 0;
}