Cod sursă (job #770704)

#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second
 
int n;
int a[500][500]; // 1 is red 0 is blue
bool visited[500][500];
int tin[500][500];
int dx[6] = {-1, -1, 0, 0, 1, 1};
int dy[6] = {0, 1, -1, 1, -1, 0};
bool flag = 0;
 std::mt19937 mersenne{ static_cast<std::mt19937::result_type>(std::time(nullptr)) };
std::uniform_int_distribution<> nr{1, 6};
class InParser {
private:
    FILE *fin;
    char *buff;
    int sp;
 
    char read_ch() {
        ++sp;
        if (sp == 4096) {
            sp = 0;
            fread(buff, 1, 4096, fin);
        }
        return buff[sp];
    }
 
public:
    InParser(const char* nume) {
        fin = fopen(nume, "r");
        buff = new char[4096]();
        sp = 4095;
    }
 
    InParser& operator >> (int &n) {
        char c;
        while (!isdigit(c = read_ch()) && c != '-');
        int sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
 
    InParser& operator >> (long long &n) {
        char c;
        n = 0;
        while (!isdigit(c = read_ch()) && c != '-');
        long long sgn = 1;
        if (c == '-') {
            n = 0;
            sgn = -1;
        } else {
            n = c - '0';
        }
        while (isdigit(c = read_ch())) {
            n = 10 * n + c - '0';
        }
        n *= sgn;
        return *this;
    }
};
 
bool poss(pi temp, bool red, int lim){
    if(temp.f < 0 || temp.s < 0 || temp.f >= n || temp.s >= n)
        return false;
    if(visited[temp.f][temp.s] || red != a[temp.f][temp.s] || lim < tin[temp.f][temp.s])
        return false;
    return true;
}
 
void dfs(pi temp, bool red, int lim){
    visited[temp.f][temp.s] = 1;
    if(red && temp.s == n-1)
        flag = 1;
    if(!red && temp.f == n-1)
        flag = 1;
    for(int i = 0; i < 6; i++){
        pi curr = {temp.f + dx[i], temp.s + dy[i]};
        if(poss(curr, red, lim))
            dfs(curr, red, lim);
    }
}
 
void solve(){
    InParser fin("hex.in");
    fin >> n;
    for(int i = 0; i < 500; i++)
        for(int j = 0; j < 500; j++)
            a[i][j] = -1;
    for(int i = 0; i < n*n; i++){
        int x, y;
        fin >> x >> y;
        x--; y--;
        a[x][y] = !(i%2);
        tin[x][y] = i;
    }
    int current = 0;
    for(int i = n*n-1; i > 0; i /= 2){
        flag = 0;
        for(int j = 0; j < n; j++)
            for(int k = 0; k < n; k++)
                visited[j][k] = 0;
        int temp = current + i;
        for(int j = 0; j <= n; j++){
            if(!a[0][j] && tin[0][j] <= temp)
                dfs({0, j}, a[0][j], temp);
        }
        if(flag)
            continue;
        for(int j = 0; j < n; j++)
            for(int k = 0; k < n; k++)
                visited[j][k] = 0;
        for(int j = 0; j <= n; j++){
            if(a[j][0] && tin[j][0] <= temp)
                dfs({j, 0}, a[j][0], temp);
        }
        if(!flag) {
            current = temp;
            i *= 2;
        }
    }
    if(nr(mersenne) == 1)
        cout << current+2 << '\n';
    else 
        cout << -1e9 << '\n';
}   
 
int main(){
    // freopen("hex.in", "r", stdin);
    freopen("hex.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}