Submission #980584

#	Time	Username	Problem	Language	Result	Execution time	Memory
980584		vjudge1	Hexagonal Territory (APIO21_hexagon)	C++17	0 / 100	1 ms	348 KiB

hexagon

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

using namespace std;

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;

const int N = 30;
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});
            }
        }
    }
}

int draw_territory(int n, int A, int B,
                   vector<int> D, vector<int> L) {
    
    for (int c : L) sumL += c;
    
    if (sumL <= 2000) {
        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;
            }
        }
        // for (int i = 0; i < 2 * N; i++) {
        //     for (int j = 0; j < 2 * N; j++) {
        //         cout << grid[i][j];
        //     }
        //     cout << '\n';
        // }
        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;
    }

    return 0;
}

Compilation message (stderr)

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

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