Submission #980621

#	Time	Username	Problem	Language	Result	Execution time	Memory
980621		vjudge1	Hexagonal Territory (APIO21_hexagon)	C++17	20 / 100	351 ms	64596 KiB

hexagon

#include <bits/stdc++.h>
#include "hexagon.h"

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;

void norm(int &x) {
    if (x >= MOD) x -= MOD;
    if (x < 0) x += MOD;
}

struct point {
    int x;
    int y;
    point() {}
    point(int x, int y) : x(x), y(y) {} 
};
pair<int, int> directions[6] = {
    {-1, -1}, {-1, 0}, {0, +1}, {+1, +1}, {+1, 0}, {0, -1}
};

point move(point a, int dir) {
    return point(a.x + directions[dir].first, 
                a.y + directions[dir].second);
}

int sumL = 0;

namespace Third {
const int N = 2020;
int grid[2 * N][2 * N] = {};

point start = {N, N};
int cnt = 0;
int sumD = 0;
bool inside(point a) {
    return (a.x >= 0 && a.x < 2 * N && a.y >= 0 && a.y < 2 * N);
}

void coloring(point a, int color) {
    grid[a.x][a.y] = color;
    queue<point> q;
    q.push(a);
    while (!q.empty()) {
        point v = q.front();
        q.pop();
        for (int i = 0; i < 6; i++) {
            point to = move(v, i);
            if (inside(to) && !grid[to.x][to.y]) {
                grid[to.x][to.y] = color;
                q.push(to);
            }

        }
    }
}
void bfs() {
    queue<pair<point, int>> q;
    q.push({start, 0});
    grid[start.x][start.y] = 3;

    while (!q.empty()) {
        point v = q.front().first;
        int d = q.front().second;
        q.pop();
        cnt++;
        sumD += d; norm(sumD);  
        for (int i = 0; i < 6; i++) {
            point to = move(v, i);
            if (!inside(to)) continue;
            if (grid[to.x][to.y] == 1 || grid[to.x][to.y] == 2) {
                grid[to.x][to.y] = 3;
                q.push({to, d + 1});
            }
        }
    }
}
};



long long binpow(long long a, long long n, long long M) {
    long long res = 1;
    for(;n;n >>= 1) {
        if(n & 1) res = (res * a) % M;
        a = (a * a) % M;
    }
    return res;
}
int draw_territory(int n, int A, int B,
                   vector<int> D, vector<int> L) {
    
    for (int c : L) sumL += c;
    
    if (sumL <= 2000) {
        using namespace Third;
        point cur = start;

        grid[cur.x][cur.y] = 2;
        int kk = 0;
        for (int i = 0; i < n; i++) {
            D[i]--;
            while (L[i]--) {
                cur = move(cur, D[i]);
                grid[cur.x][cur.y] = 2;
            }
        }
        coloring(point(0, 0), 4);
        point p(0, 0);

        for (int i = 0; i < 2 * N; i++) {
            for (int j = 0; j < 2 * N; j++) {
                if (!grid[i][j]) {
                    coloring(point(i, j), 1);
                }
            }
        }

        bfs();
        return (1ll * cnt * A % MOD + 1ll * sumD * B % MOD) % MOD;
    }

    if (n == 3) {
        
        ll ln = L[0] + 1;
        ll c = ln * (ln + 1) / 2 % MOD;
        ll d = ln * (ln + 1) % MOD * (2 * ln + 1) % MOD * binpow(6, MOD - 2, MOD) - c;
        c %= MOD, d %= MOD;
        norm(c);
        norm(d);

        return (c * A + d * B) % MOD;
    }
    return 0;
}

Compilation message (stderr)

hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:102:13: warning: unused variable 'kk' [-Wunused-variable]
  102 |         int kk = 0;
      |             ^~

• Subtask 1: 3 / 3
• Subtask 2: 6 / 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