oj.uz

Submission #961561

# Submission time Handle Problem Language Result Execution time Memory
961561 2024-04-12T08:09:32 Z Warinchai Dungeons Game (IOI21_dungeons) C++17
13 / 100
 614 ms 532816 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(pow>(1<<c)){
        lv=c;
        c++;
    }
    //cerr<<x<<"\n";
    //cerr<<lv<<"\n";
    while(1){
        //cerr<<x<<" "<<pow<<"\n";
        if(lv==25)return pow+dis[lv][25][x];
        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 92 ms 527700 KB Output is correct
2 Correct 59 ms 527816 KB Output is correct
3 Correct 59 ms 527936 KB Output is correct
4 Correct 136 ms 532068 KB Output is correct
5 Incorrect 58 ms 527956 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 527700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 527748 KB Output is correct
2 Correct 217 ms 532604 KB Output is correct
3 Correct 201 ms 532656 KB Output is correct
4 Correct 190 ms 532584 KB Output is correct
5 Correct 201 ms 532816 KB Output is correct
6 Correct 442 ms 532564 KB Output is correct
7 Correct 440 ms 532816 KB Output is correct
8 Correct 427 ms 532564 KB Output is correct
9 Correct 246 ms 532764 KB Output is correct
10 Correct 398 ms 532560 KB Output is correct
11 Correct 478 ms 532560 KB Output is correct
12 Correct 614 ms 532560 KB Output is correct
13 Correct 600 ms 532564 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 527748 KB Output is correct
2 Correct 217 ms 532604 KB Output is correct
3 Correct 201 ms 532656 KB Output is correct
4 Correct 190 ms 532584 KB Output is correct
5 Correct 201 ms 532816 KB Output is correct
6 Correct 442 ms 532564 KB Output is correct
7 Correct 440 ms 532816 KB Output is correct
8 Correct 427 ms 532564 KB Output is correct
9 Correct 246 ms 532764 KB Output is correct
10 Correct 398 ms 532560 KB Output is correct
11 Correct 478 ms 532560 KB Output is correct
12 Correct 614 ms 532560 KB Output is correct
13 Correct 600 ms 532564 KB Output is correct
14 Incorrect 59 ms 527760 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 527748 KB Output is correct
2 Correct 217 ms 532604 KB Output is correct
3 Correct 201 ms 532656 KB Output is correct
4 Correct 190 ms 532584 KB Output is correct
5 Correct 201 ms 532816 KB Output is correct
6 Correct 442 ms 532564 KB Output is correct
7 Correct 440 ms 532816 KB Output is correct
8 Correct 427 ms 532564 KB Output is correct
9 Correct 246 ms 532764 KB Output is correct
10 Correct 398 ms 532560 KB Output is correct
11 Correct 478 ms 532560 KB Output is correct
12 Correct 614 ms 532560 KB Output is correct
13 Correct 600 ms 532564 KB Output is correct
14 Incorrect 59 ms 527760 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 527700 KB Output isn't correct
2 Halted 0 ms 0 KB -