oj.uz

Submission #1016755

# Submission time Handle Problem Language Result Execution time Memory
1016755 2024-07-08T11:43:55 Z JakobZorz Dungeons Game (IOI21_dungeons) C++17
63 / 100
 3171 ms 2097152 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>>(n+1,vector<int>((pw+1)/2));
        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[n][p/2]=n;
        
        for(int i=0;i<n;i++){
            jmp[i][0]=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[i][(p-1)/2]][(p-1)/2];
                if(win[jmp[i][(p-1)/2]][(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[i][(p-1)/2]][(p-1)/2]-gain[i][(p-1)/2]));
            }
            
            for(int i=0;i<n;i++)
                jmp[i][p/2]=jmp[jmp[i][(p-1)/2]][(p-1)/2];
        }
    }
    
    // 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;p>=0;p--){
            while(jmp[x][p/2]!=n&&(1LL*win[x][p/2]>st||win[x][p/2]==1e9)&&st+gain[x][p/2]<thres){
                st+=gain[x][p/2];
                x=jmp[x][p/2];
            }
        }
        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];
 
void init(int N,vector<int>s,vector<int>p,vector<int>w,vector<int>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=0;pw<25;pw++)
        dun[pw].setup();
}
 
ll simulate(int x,int z){
    ll st=z;
    
    for(int p=0;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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 18 ms 12380 KB Output is correct
4 Correct 339 ms 299088 KB Output is correct
5 Correct 13 ms 12376 KB Output is correct
6 Correct 350 ms 298888 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6232 KB Output is correct
2 Runtime error 2468 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6236 KB Output is correct
2 Correct 407 ms 298892 KB Output is correct
3 Correct 405 ms 299080 KB Output is correct
4 Correct 395 ms 300264 KB Output is correct
5 Correct 401 ms 300036 KB Output is correct
6 Correct 619 ms 300388 KB Output is correct
7 Correct 608 ms 299092 KB Output is correct
8 Correct 1138 ms 298920 KB Output is correct
9 Correct 377 ms 299092 KB Output is correct
10 Correct 967 ms 298964 KB Output is correct
11 Correct 867 ms 298912 KB Output is correct
12 Correct 3135 ms 299024 KB Output is correct
13 Correct 3171 ms 299088 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6236 KB Output is correct
2 Correct 407 ms 298892 KB Output is correct
3 Correct 405 ms 299080 KB Output is correct
4 Correct 395 ms 300264 KB Output is correct
5 Correct 401 ms 300036 KB Output is correct
6 Correct 619 ms 300388 KB Output is correct
7 Correct 608 ms 299092 KB Output is correct
8 Correct 1138 ms 298920 KB Output is correct
9 Correct 377 ms 299092 KB Output is correct
10 Correct 967 ms 298964 KB Output is correct
11 Correct 867 ms 298912 KB Output is correct
12 Correct 3135 ms 299024 KB Output is correct
13 Correct 3171 ms 299088 KB Output is correct
14 Correct 7 ms 6232 KB Output is correct
15 Correct 389 ms 299028 KB Output is correct
16 Correct 413 ms 299108 KB Output is correct
17 Correct 501 ms 299092 KB Output is correct
18 Correct 498 ms 299092 KB Output is correct
19 Correct 621 ms 298944 KB Output is correct
20 Correct 721 ms 299092 KB Output is correct
21 Correct 860 ms 299092 KB Output is correct
22 Correct 982 ms 299104 KB Output is correct
23 Correct 1556 ms 299068 KB Output is correct
24 Correct 1837 ms 299084 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6236 KB Output is correct
2 Correct 407 ms 298892 KB Output is correct
3 Correct 405 ms 299080 KB Output is correct
4 Correct 395 ms 300264 KB Output is correct
5 Correct 401 ms 300036 KB Output is correct
6 Correct 619 ms 300388 KB Output is correct
7 Correct 608 ms 299092 KB Output is correct
8 Correct 1138 ms 298920 KB Output is correct
9 Correct 377 ms 299092 KB Output is correct
10 Correct 967 ms 298964 KB Output is correct
11 Correct 867 ms 298912 KB Output is correct
12 Correct 3135 ms 299024 KB Output is correct
13 Correct 3171 ms 299088 KB Output is correct
14 Correct 7 ms 6232 KB Output is correct
15 Correct 389 ms 299028 KB Output is correct
16 Correct 413 ms 299108 KB Output is correct
17 Correct 501 ms 299092 KB Output is correct
18 Correct 498 ms 299092 KB Output is correct
19 Correct 621 ms 298944 KB Output is correct
20 Correct 721 ms 299092 KB Output is correct
21 Correct 860 ms 299092 KB Output is correct
22 Correct 982 ms 299104 KB Output is correct
23 Correct 1556 ms 299068 KB Output is correct
24 Correct 1837 ms 299084 KB Output is correct
25 Correct 366 ms 298616 KB Output is correct
26 Correct 425 ms 298984 KB Output is correct
27 Correct 399 ms 299060 KB Output is correct
28 Correct 385 ms 299092 KB Output is correct
29 Correct 501 ms 299088 KB Output is correct
30 Correct 859 ms 298948 KB Output is correct
31 Correct 1058 ms 299088 KB Output is correct
32 Correct 1022 ms 299064 KB Output is correct
33 Correct 692 ms 299052 KB Output is correct
34 Correct 1342 ms 298836 KB Output is correct
35 Correct 951 ms 298916 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6232 KB Output is correct
2 Runtime error 2468 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -