Cod sursă (job #641481)

#include <fstream>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")

static inline int min( const int& a, const int& b ) {
    return ( a <= b ? a : b );
}

static inline int max( const int& a, const int& b ) {
    return ( a >= b ? a : b );
}

#define MAX 500
using namespace std;

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


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

struct Andrei007 {
    short minL, maxL;
};

struct point {
    short l, c;
};

Andrei007 buck[ MAX * MAX + 10 ];
int ok[ MAX + 2 ][ MAX + 2 ];
int dad[ MAX * MAX + 10 ];
int n;

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

bool unesteR( point a, point b ) {
    int tata1 = tata( ok[ a.l ][ a.c ] >> 1 );
    int tata2 = tata( ok[ b.l ][ b.c ] >> 1 );
    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;

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