Submission #1187684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187684		Aviansh	육각형 영역 (APIO21_hexagon)	C++20	11 / 100	2110 ms	441288 KiB

hexagon

#include "hexagon.h"

#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;
const int mxn = 3000;
bool vis[mxn][mxn];

long long modinv(long long x){
    int need  = mod-2;
    long long ans = 1;
    long long curr = x;
    for(int i = 0;i<32;i++){
        if((1<<i)&need){
            ans*=curr;
            ans%=mod;
        }
        curr*=curr;
        curr%=mod;
    }
    return ans;
}

void dfs(int x, int y,set<array<int,2>>&s){
    //cout << "here1" << endl;
    if(s.find({x,y})!=s.end()){
        return;
    }
    if(x<0||y<0||x>=mxn||y>=mxn){
        return;
    }
    if(vis[x][y]){
        return;
    }
    //cout << "here2" << endl;
    vis[x][y]=1;
    dfs(x-2,y,s);
    dfs(x-1,y-1,s);
    dfs(x-1,y+1,s);
    dfs(x+1,y-1,s);
    dfs(x+1,y+1,s);
    dfs(x+2,y,s);
}

int draw_territory(int n, int A, int b,vector<int> d, vector<int> l) {
    for(int i = 0;i<mxn;i++){
        fill(vis[i],vis[i]+mxn,0);
    }
    int x,y;
    x=mxn/2;
    y=mxn/2;
    set<array<int,2>>s;
    for(int i = 0;i<n;i++){
        while(l[i]){
            s.insert({x,y});
            if(d[i]==1){
                x-=2;
            }
            else if(d[i]==2){
                x--;
                y++;
            }
            else if(d[i]==3){
                x++;
                y++;
            }
            else if(d[i]==4){
                x+=2;
            }
            else if(d[i]==5){
                x++;
                y--;
            }
            else if(d[i]==6){
                x--;y--;
            }
            l[i]--;
        }
    }
    assert(x==mxn/2&&y==mxn/2);
    dfs(0,0,s);
    priority_queue<array<int,3>,vector<array<int,3>>,greater<array<int,3>>>pq;
    pq.push({0,x,y});
    long long ans = 0;
    while(!pq.empty()){
        array<int,3>a = pq.top();
        pq.pop();
        if(vis[a[1]][a[2]])
            continue;
        vis[a[1]][a[2]]=1;
        ans+=A;
        ans%=mod;
        ans+=1LL*b*a[0];
        ans%=mod;
        pq.push({a[0]+1,a[1]+2,a[2]});
        pq.push({a[0]+1,a[1]-2,a[2]});
        pq.push({a[0]+1,a[1]+1,a[2]+1});
        pq.push({a[0]+1,a[1]-1,a[2]+1});
        pq.push({a[0]+1,a[1]+1,a[2]-1});
        pq.push({a[0]+1,a[1]-1,a[2]-1});
        //cout << a[0] << " " << a[1] << " " << a[2] << endl;
    }
    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