oj.uz

Submission #1016765

# Submission time Handle Problem Language Result Execution time Memory
1016765 2024-07-08T12:01:37 Z JakobZorz Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3268 ms 1316484 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>>((pw+1)/2,vector<ll>(n+1));
        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[0][i]=st2[i];
            win[i][0]=st1[i];
        }
            
        for(int p=1;p<pw;p++){
            for(int i=0;i<n;i++){
                gain[p/2][i]=gain[(p-1)/2][i]+gain[(p-1)/2][jmp[(p-1)/2][i]];
                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[(p-1)/2][i]));
            }
            
            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[p][x]<thres){
                st+=gain[p][x];
                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 6 ms 7004 KB Output is correct
4 Correct 165 ms 164732 KB Output is correct
5 Correct 7 ms 7004 KB Output is correct
6 Correct 176 ms 164728 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3676 KB Output is correct
2 Correct 1452 ms 1316484 KB Output is correct
3 Correct 1461 ms 1316348 KB Output is correct
4 Correct 1626 ms 1316348 KB Output is correct
5 Correct 1592 ms 1316348 KB Output is correct
6 Correct 2366 ms 1316292 KB Output is correct
7 Correct 2206 ms 1316308 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3672 KB Output is correct
2 Correct 202 ms 165520 KB Output is correct
3 Correct 214 ms 165448 KB Output is correct
4 Correct 187 ms 165640 KB Output is correct
5 Correct 185 ms 165640 KB Output is correct
6 Correct 353 ms 165636 KB Output is correct
7 Correct 443 ms 165636 KB Output is correct
8 Correct 432 ms 165892 KB Output is correct
9 Correct 183 ms 165640 KB Output is correct
10 Correct 340 ms 165636 KB Output is correct
11 Correct 579 ms 165640 KB Output is correct
12 Correct 1856 ms 165516 KB Output is correct
13 Correct 1342 ms 165640 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3672 KB Output is correct
2 Correct 202 ms 165520 KB Output is correct
3 Correct 214 ms 165448 KB Output is correct
4 Correct 187 ms 165640 KB Output is correct
5 Correct 185 ms 165640 KB Output is correct
6 Correct 353 ms 165636 KB Output is correct
7 Correct 443 ms 165636 KB Output is correct
8 Correct 432 ms 165892 KB Output is correct
9 Correct 183 ms 165640 KB Output is correct
10 Correct 340 ms 165636 KB Output is correct
11 Correct 579 ms 165640 KB Output is correct
12 Correct 1856 ms 165516 KB Output is correct
13 Correct 1342 ms 165640 KB Output is correct
14 Correct 4 ms 3676 KB Output is correct
15 Correct 195 ms 165692 KB Output is correct
16 Correct 213 ms 165640 KB Output is correct
17 Correct 273 ms 165636 KB Output is correct
18 Correct 279 ms 165636 KB Output is correct
19 Correct 367 ms 165692 KB Output is correct
20 Correct 417 ms 165516 KB Output is correct
21 Correct 465 ms 165636 KB Output is correct
22 Correct 412 ms 165520 KB Output is correct
23 Correct 1094 ms 165532 KB Output is correct
24 Correct 941 ms 165636 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3672 KB Output is correct
2 Correct 202 ms 165520 KB Output is correct
3 Correct 214 ms 165448 KB Output is correct
4 Correct 187 ms 165640 KB Output is correct
5 Correct 185 ms 165640 KB Output is correct
6 Correct 353 ms 165636 KB Output is correct
7 Correct 443 ms 165636 KB Output is correct
8 Correct 432 ms 165892 KB Output is correct
9 Correct 183 ms 165640 KB Output is correct
10 Correct 340 ms 165636 KB Output is correct
11 Correct 579 ms 165640 KB Output is correct
12 Correct 1856 ms 165516 KB Output is correct
13 Correct 1342 ms 165640 KB Output is correct
14 Correct 4 ms 3676 KB Output is correct
15 Correct 195 ms 165692 KB Output is correct
16 Correct 213 ms 165640 KB Output is correct
17 Correct 273 ms 165636 KB Output is correct
18 Correct 279 ms 165636 KB Output is correct
19 Correct 367 ms 165692 KB Output is correct
20 Correct 417 ms 165516 KB Output is correct
21 Correct 465 ms 165636 KB Output is correct
22 Correct 412 ms 165520 KB Output is correct
23 Correct 1094 ms 165532 KB Output is correct
24 Correct 941 ms 165636 KB Output is correct
25 Correct 181 ms 164900 KB Output is correct
26 Correct 230 ms 165672 KB Output is correct
27 Correct 204 ms 165680 KB Output is correct
28 Correct 205 ms 165516 KB Output is correct
29 Correct 234 ms 165640 KB Output is correct
30 Correct 386 ms 165636 KB Output is correct
31 Correct 467 ms 165640 KB Output is correct
32 Correct 577 ms 165636 KB Output is correct
33 Correct 357 ms 165516 KB Output is correct
34 Correct 706 ms 165636 KB Output is correct
35 Correct 533 ms 165640 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3676 KB Output is correct
2 Correct 1452 ms 1316484 KB Output is correct
3 Correct 1461 ms 1316348 KB Output is correct
4 Correct 1626 ms 1316348 KB Output is correct
5 Correct 1592 ms 1316348 KB Output is correct
6 Correct 2366 ms 1316292 KB Output is correct
7 Correct 2206 ms 1316308 KB Output is correct
8 Correct 4 ms 3672 KB Output is correct
9 Correct 202 ms 165520 KB Output is correct
10 Correct 214 ms 165448 KB Output is correct
11 Correct 187 ms 165640 KB Output is correct
12 Correct 185 ms 165640 KB Output is correct
13 Correct 353 ms 165636 KB Output is correct
14 Correct 443 ms 165636 KB Output is correct
15 Correct 432 ms 165892 KB Output is correct
16 Correct 183 ms 165640 KB Output is correct
17 Correct 340 ms 165636 KB Output is correct
18 Correct 579 ms 165640 KB Output is correct
19 Correct 1856 ms 165516 KB Output is correct
20 Correct 1342 ms 165640 KB Output is correct
21 Correct 4 ms 3676 KB Output is correct
22 Correct 195 ms 165692 KB Output is correct
23 Correct 213 ms 165640 KB Output is correct
24 Correct 273 ms 165636 KB Output is correct
25 Correct 279 ms 165636 KB Output is correct
26 Correct 367 ms 165692 KB Output is correct
27 Correct 417 ms 165516 KB Output is correct
28 Correct 465 ms 165636 KB Output is correct
29 Correct 412 ms 165520 KB Output is correct
30 Correct 1094 ms 165532 KB Output is correct
31 Correct 941 ms 165636 KB Output is correct
32 Correct 181 ms 164900 KB Output is correct
33 Correct 230 ms 165672 KB Output is correct
34 Correct 204 ms 165680 KB Output is correct
35 Correct 205 ms 165516 KB Output is correct
36 Correct 234 ms 165640 KB Output is correct
37 Correct 386 ms 165636 KB Output is correct
38 Correct 467 ms 165640 KB Output is correct
39 Correct 577 ms 165636 KB Output is correct
40 Correct 357 ms 165516 KB Output is correct
41 Correct 706 ms 165636 KB Output is correct
42 Correct 533 ms 165640 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 5 ms 3676 KB Output is correct
45 Correct 1671 ms 1316332 KB Output is correct
46 Correct 1514 ms 1316312 KB Output is correct
47 Correct 1581 ms 1316340 KB Output is correct
48 Correct 1452 ms 1316336 KB Output is correct
49 Correct 1770 ms 1316420 KB Output is correct
50 Correct 1940 ms 1316332 KB Output is correct
51 Correct 1394 ms 1316476 KB Output is correct
52 Correct 3268 ms 1316356 KB Output is correct
53 Correct 3094 ms 1316372 KB Output is correct
54 Correct 1898 ms 1316428 KB Output is correct
55 Correct 2796 ms 1316352 KB Output is correct
56 Correct 2430 ms 1316324 KB Output is correct
57 Correct 2463 ms 1316324 KB Output is correct
58 Correct 2439 ms 1316336 KB Output is correct
59 Correct 2508 ms 1316464 KB Output is correct
60 Correct 2498 ms 1316400 KB Output is correct
61 Correct 2830 ms 1316300 KB Output is correct