oj.uz

Submission #1016764

# Submission time Handle Problem Language Result Execution time Memory
1016764 2024-07-08T11:59:53 Z JakobZorz Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4251 ms 1550896 KB 
#include"dungeons.h"
#include<vector>
#include<iostream>
typedef long long ll;
using namespace std;
 
int n;
 
struct Dungeon{
    vector<int>nxt1; // win
    vector<int>nxt2; // lose
    vector<int>st1;  // strength
    vector<int>st2;  // gain on losing
    vector<vector<int>>jmp; // where to jump?
    vector<vector<ll>>gain; // strength gain of that jump
    vector<vector<int>>win;  // strength requirement to win in that jump
    int pw;
    ll thres=0;
    
    Dungeon(int n):nxt1(n),nxt2(n),st1(n),st2(n){}
    Dungeon()=default;
    
    void setup(){
        jmp=vector<vector<int>>((pw+1)/2,vector<int>(n+1));
        gain=vector<vector<ll>>(n+1,vector<ll>((pw+1)/2));
        win=vector<vector<int>>(n+1,vector<int>((pw+1)/2));
        for(int p=0;p<pw;p++)
            jmp[p/2][n]=n;
        
        for(int i=0;i<n;i++){
            jmp[0][i]=nxt2[i];
            gain[i][0]=st2[i];
            win[i][0]=st1[i];
        }
            
        for(int p=1;p<pw;p++){
            for(int i=0;i<n;i++){
                gain[i][p/2]=gain[i][(p-1)/2]+gain[jmp[(p-1)/2][i]][(p-1)/2];
                if(win[jmp[(p-1)/2][i]][(p-1)/2]==1e9)
                    win[i][p/2]=win[i][(p-1)/2];
                else
                    win[i][p/2]=max(0LL,min(1LL*win[i][(p-1)/2],1LL*win[jmp[(p-1)/2][i]][(p-1)/2]-gain[i][(p-1)/2]));
            }
            
            for(int i=0;i<n;i++)
                jmp[p/2][i]=jmp[(p-1)/2][jmp[(p-1)/2][i]];
        }
    }
    
    // simulate until it either reaches n-th node, wins, or strength>=thres
    pair<int,ll>simulate(int x,ll st){
        for(int p=(pw-1)/2;p>=0;p--){
            while(jmp[p][x]!=n&&(1LL*win[x][p]>st||win[x][p]==1e9)&&st+gain[x][p]<thres){
                st+=gain[x][p];
                x=jmp[p][x];
            }
        }
        while(x!=n&&st<thres){
            // do 1 more jump
            if(st>=st1[x]&&st1[x]!=1e9){
                st+=st1[x];
                x=nxt1[x];
                break;
            }else{
                st+=st2[x];
                x=nxt2[x];
            }
        }
        return{x,st};
    }
};
 
Dungeon dun[25];
vector<int>s,p,w,l;

void init(int N,vector<int>S,vector<int>P,vector<int>W,vector<int>L){
    s=S;
    p=P;
    w=W;
    l=L;
    n=N;
    
    for(int pw=0;pw<25;pw++){
        dun[pw]=Dungeon(n);
        dun[pw].thres=2LL<<pw;
        dun[pw].pw=pw+1;
        for(int i=0;i<n;i++){
            if(s[i]<=1<<pw){
                dun[pw].nxt1[i]=0;
                dun[pw].nxt2[i]=w[i];
                dun[pw].st1[i]=1e9;
                dun[pw].st2[i]=s[i];
            }else if(s[i]>=2<<pw){
                dun[pw].nxt1[i]=0;
                dun[pw].nxt2[i]=l[i];
                dun[pw].st1[i]=1e9;
                dun[pw].st2[i]=p[i];
            }else{
                dun[pw].nxt1[i]=w[i];
                dun[pw].nxt2[i]=l[i];
                dun[pw].st1[i]=s[i];
                dun[pw].st2[i]=p[i];
            }
        }
    }
    dun[24].thres=1e18;
    for(int pw=9;pw<25;pw++)
        dun[pw].setup();
}
 
ll simulate(int x,int z){
    ll st=z;
    while(x!=n&&st<(1<<9)){
        // do 1 more jump
        if(st>=s[x]&&s[x]!=1e9){
            st+=s[x];
            x=w[x];
        }else{
            st+=p[x];
            x=l[x];
        }
    }
    
    for(int p=9;p<25;p++){
        while(x!=n&&st<2LL<<p){
            auto r=dun[p].simulate(x,st);
            x=r.first;
            st=r.second;
        }
    }
    
    return st;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 7 ms 8028 KB Output is correct
4 Correct 214 ms 192908 KB Output is correct
5 Correct 8 ms 8028 KB Output is correct
6 Correct 226 ms 193168 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4188 KB Output is correct
2 Correct 2192 ms 1541716 KB Output is correct
3 Correct 2111 ms 1541932 KB Output is correct
4 Correct 2288 ms 1542072 KB Output is correct
5 Correct 2236 ms 1541696 KB Output is correct
6 Correct 3195 ms 1541768 KB Output is correct
7 Correct 3068 ms 1541924 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 267 ms 193816 KB Output is correct
3 Correct 265 ms 193676 KB Output is correct
4 Correct 258 ms 193680 KB Output is correct
5 Correct 246 ms 193664 KB Output is correct
6 Correct 442 ms 193680 KB Output is correct
7 Correct 508 ms 193680 KB Output is correct
8 Correct 474 ms 193676 KB Output is correct
9 Correct 261 ms 193932 KB Output is correct
10 Correct 420 ms 193676 KB Output is correct
11 Correct 684 ms 193808 KB Output is correct
12 Correct 2200 ms 193676 KB Output is correct
13 Correct 1610 ms 193744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 267 ms 193816 KB Output is correct
3 Correct 265 ms 193676 KB Output is correct
4 Correct 258 ms 193680 KB Output is correct
5 Correct 246 ms 193664 KB Output is correct
6 Correct 442 ms 193680 KB Output is correct
7 Correct 508 ms 193680 KB Output is correct
8 Correct 474 ms 193676 KB Output is correct
9 Correct 261 ms 193932 KB Output is correct
10 Correct 420 ms 193676 KB Output is correct
11 Correct 684 ms 193808 KB Output is correct
12 Correct 2200 ms 193676 KB Output is correct
13 Correct 1610 ms 193744 KB Output is correct
14 Correct 4 ms 4188 KB Output is correct
15 Correct 252 ms 193640 KB Output is correct
16 Correct 267 ms 193816 KB Output is correct
17 Correct 320 ms 193680 KB Output is correct
18 Correct 334 ms 193680 KB Output is correct
19 Correct 431 ms 193684 KB Output is correct
20 Correct 445 ms 193676 KB Output is correct
21 Correct 534 ms 193680 KB Output is correct
22 Correct 461 ms 193676 KB Output is correct
23 Correct 1139 ms 193684 KB Output is correct
24 Correct 1254 ms 194064 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4440 KB Output is correct
2 Correct 267 ms 193816 KB Output is correct
3 Correct 265 ms 193676 KB Output is correct
4 Correct 258 ms 193680 KB Output is correct
5 Correct 246 ms 193664 KB Output is correct
6 Correct 442 ms 193680 KB Output is correct
7 Correct 508 ms 193680 KB Output is correct
8 Correct 474 ms 193676 KB Output is correct
9 Correct 261 ms 193932 KB Output is correct
10 Correct 420 ms 193676 KB Output is correct
11 Correct 684 ms 193808 KB Output is correct
12 Correct 2200 ms 193676 KB Output is correct
13 Correct 1610 ms 193744 KB Output is correct
14 Correct 4 ms 4188 KB Output is correct
15 Correct 252 ms 193640 KB Output is correct
16 Correct 267 ms 193816 KB Output is correct
17 Correct 320 ms 193680 KB Output is correct
18 Correct 334 ms 193680 KB Output is correct
19 Correct 431 ms 193684 KB Output is correct
20 Correct 445 ms 193676 KB Output is correct
21 Correct 534 ms 193680 KB Output is correct
22 Correct 461 ms 193676 KB Output is correct
23 Correct 1139 ms 193684 KB Output is correct
24 Correct 1254 ms 194064 KB Output is correct
25 Correct 245 ms 192912 KB Output is correct
26 Correct 291 ms 193812 KB Output is correct
27 Correct 258 ms 193684 KB Output is correct
28 Correct 274 ms 193736 KB Output is correct
29 Correct 292 ms 193680 KB Output is correct
30 Correct 480 ms 193676 KB Output is correct
31 Correct 694 ms 193812 KB Output is correct
32 Correct 765 ms 193856 KB Output is correct
33 Correct 402 ms 193680 KB Output is correct
34 Correct 832 ms 193780 KB Output is correct
35 Correct 662 ms 193672 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4188 KB Output is correct
2 Correct 2192 ms 1541716 KB Output is correct
3 Correct 2111 ms 1541932 KB Output is correct
4 Correct 2288 ms 1542072 KB Output is correct
5 Correct 2236 ms 1541696 KB Output is correct
6 Correct 3195 ms 1541768 KB Output is correct
7 Correct 3068 ms 1541924 KB Output is correct
8 Correct 4 ms 4440 KB Output is correct
9 Correct 267 ms 193816 KB Output is correct
10 Correct 265 ms 193676 KB Output is correct
11 Correct 258 ms 193680 KB Output is correct
12 Correct 246 ms 193664 KB Output is correct
13 Correct 442 ms 193680 KB Output is correct
14 Correct 508 ms 193680 KB Output is correct
15 Correct 474 ms 193676 KB Output is correct
16 Correct 261 ms 193932 KB Output is correct
17 Correct 420 ms 193676 KB Output is correct
18 Correct 684 ms 193808 KB Output is correct
19 Correct 2200 ms 193676 KB Output is correct
20 Correct 1610 ms 193744 KB Output is correct
21 Correct 4 ms 4188 KB Output is correct
22 Correct 252 ms 193640 KB Output is correct
23 Correct 267 ms 193816 KB Output is correct
24 Correct 320 ms 193680 KB Output is correct
25 Correct 334 ms 193680 KB Output is correct
26 Correct 431 ms 193684 KB Output is correct
27 Correct 445 ms 193676 KB Output is correct
28 Correct 534 ms 193680 KB Output is correct
29 Correct 461 ms 193676 KB Output is correct
30 Correct 1139 ms 193684 KB Output is correct
31 Correct 1254 ms 194064 KB Output is correct
32 Correct 245 ms 192912 KB Output is correct
33 Correct 291 ms 193812 KB Output is correct
34 Correct 258 ms 193684 KB Output is correct
35 Correct 274 ms 193736 KB Output is correct
36 Correct 292 ms 193680 KB Output is correct
37 Correct 480 ms 193676 KB Output is correct
38 Correct 694 ms 193812 KB Output is correct
39 Correct 765 ms 193856 KB Output is correct
40 Correct 402 ms 193680 KB Output is correct
41 Correct 832 ms 193780 KB Output is correct
42 Correct 662 ms 193672 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 4 ms 4068 KB Output is correct
45 Correct 2559 ms 1541928 KB Output is correct
46 Correct 2244 ms 1541764 KB Output is correct
47 Correct 2229 ms 1541688 KB Output is correct
48 Correct 2479 ms 1541920 KB Output is correct
49 Correct 2718 ms 1541988 KB Output is correct
50 Correct 2723 ms 1541684 KB Output is correct
51 Correct 1938 ms 1541688 KB Output is correct
52 Correct 4251 ms 1541684 KB Output is correct
53 Correct 4034 ms 1549876 KB Output is correct
54 Correct 2775 ms 1550896 KB Output is correct
55 Correct 3739 ms 1550100 KB Output is correct
56 Correct 3578 ms 1550644 KB Output is correct
57 Correct 3629 ms 1550580 KB Output is correct
58 Correct 3958 ms 1550740 KB Output is correct
59 Correct 3496 ms 1550852 KB Output is correct
60 Correct 3613 ms 1550136 KB Output is correct
61 Correct 3978 ms 1550096 KB Output is correct