Cod sursă (job #641355)

#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 ];
int okR[ MAX + 1 ][ MAX + 1 ];
int okB[ MAX + 1 ][ MAX + 1 ];
int dad[ MAX * MAX ];
int n;

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;

    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 ) {
            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 }, { (short)(l + dl[ d ]), ( short)(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 }, { (short)(l + dl[ d ]), ( short)(c + dc[ d ]) } ) ) {
                        cout << i << '\n';
                        exit( 0 );
                    }
        }
    }
    cout << k << '\n';
    return 0;
}