Submission #1072227

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072227		Ahmed57	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5551 ms	2011172 KiB

dungeons

#include "bits/stdc++.h"
 
using namespace std;
//#define int long long
#pragma GCC optimize("Ofast")
int K = 3;
array<long long,3> P[400001][14][15];
long long inf = 1e18 , N;
vector<long long> S , PP , W , L;
vector<long long> v;
void init(int n, vector<int> s, vector<int> p, vector<int> w,vector<int> l){
    for(auto i:s)S.push_back(i);
    for(auto i:p)PP.push_back(i);
    for(auto i:w)W.push_back(i);
    for(auto i:l)L.push_back(i);
    int cnt = 0;N = n;
    bool ss = 0;int cst = 0;
    while(cst<=1e7){
        cst*=4;
        if(ss){
            cst = max(cst,1);
        }
        //cout<<cst<<" "<<cnt<<endl;
        v.push_back(cst);
        ss = 1;
        for(int i = 0;i<n;i++){
            if(s[i]<=cst){
                P[i][cnt][0] = {w[i],s[i],inf};
            }else{
                P[i][cnt][0] = {l[i],p[i],s[i]};
            }
        }
        P[n][cnt][0] = {n,0,-inf};
        for(int j = 1;j<=14;j++){
            for(int i = 0;i<=n;i++){
                long long pos = i , sum = 0 , nah = inf;
                for(int e = 0;e<K;e++){
                    nah = min(nah,P[pos][cnt][j-1][2]-sum);
                    sum += P[pos][cnt][j-1][1];
                    pos = P[pos][cnt][j-1][0];
                }
                P[i][cnt][j] = {pos,sum,nah};
            }
        }
        cnt++;
    }
}
long long simulate(int x, int z) {
    long long sum = z;
    int cnt = 0;
    while(x!=N){
        //if(cnt<1000)cout<<sum<<endl;
        cnt++;
        long long nah = lower_bound(v.begin(),v.end(),sum+1)-v.begin();
        nah--;
        if(nah>26){
            return -1;
        }
        for(int i = 14;i>=0;i--){
            for(int e = 0;e<K-1;e++){
                if(P[x][nah][i][2]>sum){
                    sum+=P[x][nah][i][1];
                    x = P[x][nah][i][0];
                }
            }
        }
        if(x==N)break;
        //cout<<sum<<" "<<x<<" "<<nah<<endl;
        if(sum>=S[x]){
            sum+=S[x];
            x = W[x];
        }else{
            sum+=PP[x];
            x = L[x];
        }
    }
    //cout<<cnt<<endl;
    return sum;
}

• Subtask 1: 11 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11