Submission #984366

#	Time	Username	Problem	Language	Result	Execution time	Memory
984366		bachhoangxuan	Hexagonal Territory (APIO21_hexagon)	C++17	66 / 100	2116 ms	461076 KiB

hexagon

#include "hexagon.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int inf = 1e9;
const int mod = 1e9+7;
const int inv2 = (mod+1)/2;
const int inv3 = (mod+1)/3;
int dx[]={0,0,1,1,0,-1,-1},
    dy[]={0,1,1,0,-1,-1,0};

i32 draw_territory(i32 N, i32 A, i32 B,
                   std::vector<i32> D, std::vector<i32> L) {
    int X=0,Y=0;
    int a=0,b=0;
    for(int i=0;i<N;i++){
        b+=L[i];
        int nX=X+L[i]*dx[D[i]];
        int nY=Y+L[i]*dy[D[i]];
        a+=X*nY-Y*nX;
        X=nX;Y=nY;
    }
    a=(abs(a)+b)%mod;
    a=a*inv2%mod;
    a=(a+1)%mod;

    int T=0;
    if(B){
        if(N==3){
            int S=L[0];
            int d1=(S*(S+1)/2)%mod;
            int d2=d1*(2*S+1)%mod*inv3%mod;
            T=(d1+d2)%mod;
        }
        else{
            X=0,Y=0;
            vector<pii> p;
            set<pii> ss;
            for(int i=0;i<N;i++){
                for(int j=0;j<L[i];j++){
                    X+=dx[D[i]];
                    Y+=dy[D[i]];
                    p.push_back({X,Y});
                    for(int t=1;t<=6;t++) ss.insert({X+dx[t],Y+dy[t]});
                }
            }
            for(pii x:p) ss.erase(x);

            set<pii> outers;
            queue<pii> q;
            q.push(*ss.begin());
            outers.insert(*ss.begin());

            while(!q.empty()){
                auto [x,y]=q.front();q.pop();
                for(int t=1;t<=6;t++){
                    pii cc={x+dx[t],y+dy[t]};
                    if(ss.find(cc)!=ss.end() && outers.find(cc)==outers.end()){
                        q.push(cc);
                        outers.insert(cc);
                    }
                }
            }

            map<int,vector<int>> mp;
            for(pii x:p){
                if(outers.find({x.fi,x.se-1})!=outers.end()) mp[x.fi].push_back(x.se);
                if(outers.find({x.fi,x.se+1})!=outers.end()) mp[x.fi].push_back(x.se);
            }

            int rt=-1,M=0;
            vector<int> cx;
            vector<pii> range;
            vector<vector<int>> edge;

            int px=-inf;
            vector<pii> pre;
            for(auto [x,v]:mp){
                sort(v.begin(),v.end());
                vector<pii> cc;
                for(int i=0;i<(int)v.size();i+=2){
                    cc.push_back({v[i],v[i+1]});
                    //cout << x << ' ' << v[i] << ' ' << v[i+1] << '\n';
                }
                if(px+1==x){
                    int pos=0,S=M-(int)pre.size();
                    for(auto p:cc){
                        int l=p.fi,r=p.se;
                        if(x==0 && l<=0 && 0<=r) rt=M;
                        cx.push_back(x);
                        edge.push_back({});
                        range.push_back({l,r});

                        while(pos<(int)pre.size() && pre[pos].se+1<l) pos++;
                        int lst=pos;
                        while(pos<(int)pre.size() && pre[pos].fi<=r){
                            edge[S+pos].push_back(M);
                            edge[M].push_back(S+pos);
                            lst=pos++;
                        }
                        pos=lst;M++;
                    }
                }
                else{
                    for(auto p:cc){
                        if(x==0 && p.fi<=0 && 0<=p.se) rt=M;
                        cx.push_back(x);
                        edge.push_back({});
                        range.push_back({p.fi,p.se});
                        M++;
                    }
                }
                px=x;pre=cc;
            }
            function<void(int,int,int,int,int)> dfs = [&](int u,int p,int l,int r,int d){
                auto [L,R]=range[u];
                //cout << u << ' ' << l << ' ' << r << ' ' << d << '\n';
                T=(T+(R-L+1)*d+(l-L)*(l-L+1)/2+(R-r)*(R-r+1)/2)%mod;
                for(int v:edge[u]){
                    if(v==p) continue;
                    auto [nL,nR]=range[v];
                    int nl=l-(cx[v]<cx[u]),nr=r+(cx[v]>cx[u]);
                    int cl=max(nl,nL),cr=min(nr,nR);
                    if(cl<=cr) dfs(v,u,cl,cr,d+1);
                    else if(nr<nL) dfs(v,u,nL,nL,d+nL-nr+1);
                    else dfs(v,u,nR,nR,d+nl-nR+1);
                }
            };
            dfs(rt,-1,0,0,0);
        }
    }
    return (a*A+T*B)%mod;
}
#undef int

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