oj.uz

Submission #961513

# Submission time Handle Problem Language Result Execution time Memory
961513 2024-04-12T07:43:17 Z Warinchai Dungeons Game (IOI21_dungeons) C++17
0 / 100
 1123 ms 1076224 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[26][26][50005];
int mn[26][26][50005];
long long dis[26][26][50005];
long long inf=1e18+7;
int N;
vector<int>W;
vector<int>S;
vector<int>L;
vector<int>P;
int X=0;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
    N=n;
    S=s;
    W=w;
    L=l;
    P=p;
    //cerr<<"work\n";
    for(int i=0;i<=25;i++){
        int st=(1<<(i-1))+1;
        int en=(1<<i);
        for(int j=0;j<n;j++){
            if(s[j]>en)lift[i][0][j]=l[j],mn[i][0][j]=inf,dis[i][0][j]=p[j];
            else if(s[j]>=st)lift[i][0][j]=l[j],mn[i][0][j]=s[j],dis[i][0][j]=p[j];
            else lift[i][0][j]=w[j],mn[i][0][j]=inf,dis[i][0][j]=s[j];
        }
        lift[i][0][n]=n;
        mn[i][0][n]=0;
        for(int j=1;j<=25;j++){
            for(int k=0;k<=n;k++){
                //cerr<<i<<" "<<j<<" "<<k<<"\n";
                lift[i][j][k]=lift[i][j-1][lift[i][j-1][k]];
                dis[i][j][k]=dis[i][j-1][k]+dis[i][j-1][lift[i][j-1][k]];
                X=mn[i][j-1][lift[i][j-1][k]]-dis[i][j-1][k];
                if(dis[i][j-1][k]>mn[i][j-1][lift[i][j-1][k]])mn[i][j][k]=0;
                else mn[i][j][k]=min(mn[i][j-1][k],X);
            }
        }
    }
    //cerr<<"work\n";
	return;
}

long long simulate(int x, int z) {
    //cerr<<"work\n";
    long long c=0,lv=0;
    long long pow=z;
    while(x>(1<<c)){
        lv=c;
        c++;
    }
    //cerr<<x<<"\n";
    //cerr<<lv<<"\n";
    while(1){
        //cerr<<x<<" "<<pow<<"\n";
        assert(lv<=25);
        for(int i=25;i>=0;i--){
            //cerr<<i<<" "<<lv<<" "<<x<<"\n";
            if(pow<mn[lv][i][x]&&pow+dis[lv][i][x]<=(1<<lv))pow+=dis[lv][i][x],x=lift[lv][i][x];
        }
        //cerr<<x<<" "<<pow<<"\n\n";
        if(x==N)break;
        if(pow>=S[x])pow+=S[x],x=W[x];
        else {
            pow+=P[x];
            x=L[x];
        }
        lv++;
    }
	return pow;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 245284 KB Output is correct
2 Correct 28 ms 243544 KB Output is correct
3 Correct 36 ms 255056 KB Output is correct
4 Runtime error 805 ms 1058232 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 249256 KB Output is correct
2 Runtime error 1123 ms 1076224 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 249172 KB Output is correct
2 Runtime error 659 ms 1059152 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 249172 KB Output is correct
2 Runtime error 659 ms 1059152 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 249172 KB Output is correct
2 Runtime error 659 ms 1059152 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 249256 KB Output is correct
2 Runtime error 1123 ms 1076224 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -