Submission #1063988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063988		12345678	Hexagonal Territory (APIO21_hexagon)	C++17	11 / 100	187 ms	159828 KiB

hexagon

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

using namespace std;

#define ll long long

const ll nx=2505, mod=1e9+7;

ll a, b, k, cnt, dp[nx][nx], x, y, dx[]={1, -1, 0, 0, 1, -1}, dy[]={0, 0, 1, -1, -1, 1}, res, used[nx][nx];
bool vs[nx][nx];

int draw_territory(int N, int A, int B, std::vector<int> D, std::vector<int> L) {
    a=A, b=B;
    x=1200, y=1200;
    vs[x][y]=1;
    for (int i=0; i<N; i++)
    {
        if (D[i]==1)
        {
            while (L[i]--) y++, vs[x][y]=1;
        }
        if (D[i]==2)
        {
            while (L[i]--) x++, vs[x][y]=1;
        }
        if (D[i]==3)
        {
            while (L[i]--) x++, y--, vs[x][y]=1;
        }
        if (D[i]==4)
        {
            while (L[i]--) y--, vs[x][y]=1;
        }
        if (D[i]==5)
        {
            while (L[i]--) x--, vs[x][y]=1;
        }
        if (D[i]==6)
        {
            while (L[i]--) x--, y++, vs[x][y]=1;
        }
    }
    queue<pair<int, int>> q;
    q.push({0, 0});
    used[0][0]=1;
    while (!q.empty())
    {
        auto [x, y]=q.front();
        q.pop();
        for (int i=0; i<6; i++)
        {
            int cx=x+dx[i], cy=y+dy[i];
            if (cx<0||cy<0||cx>=nx||cy>=nx||vs[cx][cy]||used[cx][cy]) continue;
            used[cx][cy]=1;
            q.push({cx, cy});
        }
    }
    while (!q.empty()) q.pop();
    for (int i=0;i <nx;i ++) for (int j=0; j<nx;j ++) if (!used[i][j]) vs[i][j]=1, cnt++;
    //cout<<"cnt "<<cnt<<'\n';
    res+=a;
    q.push({1200, 1200});
    vs[1200][1200]=0;
    while (!q.empty())
    {
        auto [x, y]=q.front();
        q.pop();
        for (int i=0; i<6; i++)
        {
            int cx=x+dx[i], cy=y+dy[i];
            if (!vs[cx][cy]) continue;
            vs[cx][cy]=0;
            dp[cx][cy]=dp[x][y]+1;
            res=(res+a+b*dp[cx][cy])%mod;
            q.push({cx, cy});
        }
    }
    return res;
}

• 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