Submission #1198027

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198027		adiyer	Hexagonal Territory (APIO21_hexagon)	C++20	11 / 100	153 ms	91820 KiB

hexagon

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int dx[6] = {0, 1, 1, 0, -1, -1};
const int dy[6] = {2, 1, -1, -2, -1, 1};
const int mod = 1e9 + 7;
const int N = 1e5 + 11;
const int inf = 1e9 + 11;

ll bpm(ll a, ll b, ll m){
    ll c = 1;
    while(b){
        if(b & 1) c *= a, c %= m;
        a *= a, a %= m, b >>= 1;
    }
    return c;
}

ll res, a, b;

int mnx[N], mny[N], mxx[N], mxy[N];
int d[4005][4005];

bool was[4005][4005], best[4005][4005], bad[4005][4005];

void bfs(int sx, int sy){
    queue < pair < int, int > > q;
    q.push({sx, sy}), bad[sx][sy] = 1;
    while(!q.empty()){
        auto [vx, vy] = q.front();
        q.pop();
        for(int i = 0; i < 6; i++){
            int nx = vx + dx[i], ny = vy + dy[i];
            if(nx >= 0 && ny >= 0 && nx <= 4001 && ny <= 4001 && !bad[nx][ny] && !best[nx][ny]){
                bad[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}

void dist(int sx, int sy){   
    queue < pair < int, int > > q;
    q.push({sx, sy}), was[sx][sy] = 1;
    while(!q.empty()){
        auto [vx, vy] = q.front();
        res += a + d[vx][vy] * b, res %= mod;
        q.pop();
        for(int i = 0; i < 6; i++){
            int nx = vx + dx[i], ny = vy + dy[i];
            if(nx >= 0 && ny >= 0 && !bad[nx][ny] && !was[nx][ny]){
                d[nx][ny] = d[vx][vy] + 1, was[nx][ny] = 1;
                q.push({nx, ny});
            }
        }
    }
}

int draw_territory(int N, int A, int B, vector < int > D, vector < int > L) {
    a = A, b = B;
    int x = 2000, y = 2000;
    for(int i = 0; i < N; i++){
        D[i]--;
        for(int j = 0; j < L[i]; j++) best[x][y] = 1, x += dx[D[i]], y += dy[D[i]];
    }
    bfs(4001, 4001);
    dist(2000, 2000);
    int ans = res;
    return ans;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 11 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 19
• Subtask 7: 0 / 18
• Subtask 8: 0 / 16