oj.uz

Submission #984365

# Submission time Handle Problem Language Result Execution time Memory
984365 2024-05-16T14:52:49 Z bachhoangxuan Hexagonal Territory (APIO21_hexagon) C++17
42 / 100
 2000 ms 507532 KB 
#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;
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;

    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,T=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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2025 ms 478672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2056 ms 496536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 920 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 700 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 600 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 3 ms 1116 KB Output is correct
19 Correct 3 ms 1116 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 49184 KB Output is correct
2 Correct 231 ms 30400 KB Output is correct
3 Correct 290 ms 39604 KB Output is correct
4 Correct 220 ms 31072 KB Output is correct
5 Correct 348 ms 43188 KB Output is correct
6 Correct 400 ms 57980 KB Output is correct
7 Correct 154 ms 19856 KB Output is correct
8 Correct 318 ms 44664 KB Output is correct
9 Correct 406 ms 57784 KB Output is correct
10 Correct 427 ms 59080 KB Output is correct
11 Correct 312 ms 50108 KB Output is correct
12 Correct 351 ms 51368 KB Output is correct
13 Correct 329 ms 50924 KB Output is correct
14 Correct 387 ms 53128 KB Output is correct
15 Correct 218 ms 22708 KB Output is correct
16 Correct 353 ms 44588 KB Output is correct
17 Correct 471 ms 70068 KB Output is correct
18 Correct 439 ms 71028 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 507532 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 2 ms 700 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 3 ms 860 KB Output is correct
10 Correct 3 ms 760 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 3 ms 856 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 3 ms 860 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 431 ms 47952 KB Output is correct
19 Correct 237 ms 30248 KB Output is correct
20 Correct 291 ms 39864 KB Output is correct
21 Correct 223 ms 31164 KB Output is correct
22 Correct 350 ms 43444 KB Output is correct
23 Correct 402 ms 57272 KB Output is correct
24 Correct 152 ms 19904 KB Output is correct
25 Correct 302 ms 44724 KB Output is correct
26 Correct 404 ms 58036 KB Output is correct
27 Correct 415 ms 57920 KB Output is correct
28 Correct 315 ms 50620 KB Output is correct
29 Correct 346 ms 51408 KB Output is correct
30 Correct 328 ms 50364 KB Output is correct
31 Correct 382 ms 52664 KB Output is correct
32 Correct 218 ms 22248 KB Output is correct
33 Correct 331 ms 44428 KB Output is correct
34 Correct 193 ms 33776 KB Output is correct
35 Correct 219 ms 28348 KB Output is correct
36 Correct 189 ms 26816 KB Output is correct
37 Correct 289 ms 42776 KB Output is correct
38 Correct 336 ms 44416 KB Output is correct
39 Correct 343 ms 49084 KB Output is correct
40 Correct 348 ms 42680 KB Output is correct
41 Correct 296 ms 46184 KB Output is correct
42 Correct 400 ms 51228 KB Output is correct
43 Correct 407 ms 56508 KB Output is correct
44 Correct 310 ms 54332 KB Output is correct
45 Correct 297 ms 44412 KB Output is correct
46 Correct 270 ms 43032 KB Output is correct
47 Correct 249 ms 31928 KB Output is correct
48 Correct 369 ms 47408 KB Output is correct
49 Correct 337 ms 52660 KB Output is correct
50 Correct 479 ms 71124 KB Output is correct
51 Correct 439 ms 69924 KB Output is correct
52 Correct 1 ms 344 KB Output is correct
53 Correct 491 ms 71536 KB Output is correct
54 Correct 442 ms 70660 KB Output is correct
55 Correct 3 ms 1112 KB Output is correct
56 Correct 3 ms 1116 KB Output is correct
57 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 495516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 2076 ms 493412 KB Time limit exceeded
3 Halted 0 ms 0 KB -