Submission #1202329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202329		jer033	Hexagonal Territory (APIO21_hexagon)	C++20	0 / 100	428 ms	152236 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const ll MOD = 1'000'000'007;

bool bounds(int valx, int valy)
{
    if (valx<0)
        return 0;
    if (valy<0)
        return 0;
    if (valx>4400)
        return 0;
    if (valy>4400)
        return 0;
    return 1;
}

int report(ll ans)
{
    ll x = ans%MOD;
    int y = x;
    return y;
}

ll total = 0;

void score(int A, int B, ll d)
{
    ll aa = A;
    ll bb = B;
    ll dd = (d*bb)%MOD;
    total = (total+dd+aa)%MOD;
}

vector<vector<ll>> grid(4401, vector<ll> (4401, MOD));
vector<int> dx = {0, 0, 1, 1, 0, -1, -1};
vector<int> dy = {0, 1, 1, 0, -1, -1, 0};

int draw_territory(int N, int A, int B, std::vector<int> D, std::vector<int> L) {
    int currx = 2200;
    int curry = 2200;
    for (int mov = 0; mov < N; mov++)
        for (int step = 0; step < L[mov]; step++)
        {
            currx += dx[D[mov]];
            curry += dy[D[mov]];
            grid[currx][curry] = 2*MOD;
        }
    queue<pii> cells;
    cells.push({0, 0});
    grid[0][0] = 0-MOD;
    while (!cells.empty())
    {
        pii coords = cells.front();
        cells.pop();
        int xx = coords.first;
        int yy = coords.second;
        for (int i=1; i<=6; i++)
        {
            int xxx=xx+dx[i]; int yyy=yy+dy[i];
            if ((bounds(xxx, yyy)) and (grid[xxx][yyy] == MOD))
            {
                grid[xxx][yyy] = 0-MOD;
                cells.push({xxx, yyy});
            }
        }
    }
    
    grid[2200][2200] = 0;
    cells.push({2200, 2200});
    score(A, B, 0);

    while (!cells.empty())
    {
        pii coords = cells.front();
        cells.pop();
        int xx = coords.first;
        int yy = coords.second;
        for (int i=1; i<=6; i++)
        {
            int xxx=xx+dx[i]; int yyy=yy+dy[i];
            if ((bounds(xxx, yyy)) and (grid[xxx][yyy] == (2*MOD)))
            {
                grid[xxx][yyy] = grid[xx][yy]+1;
                cells.push({xxx, yyy});
                score(A, B, grid[xxx][yyy]);
            }
        }
    }

    report(total);
}

Compilation message (stderr)

hexagon.cpp: In function 'int draw_territory(int, int, int, std::vector<int>, std::vector<int>)':
hexagon.cpp:96:1: warning: no return statement in function returning non-void [-Wreturn-type]
   96 | }
      | ^

• 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