oj.uz

Submission #961549

# Submission time Handle Problem Language Result Execution time Memory
961549 2024-04-12T07:54:21 Z Warinchai Dungeons Game (IOI21_dungeons) C++17
13 / 100
 1298 ms 1076392 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";
        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 119 ms 247376 KB Output is correct
2 Correct 27 ms 247380 KB Output is correct
3 Correct 37 ms 259028 KB Output is correct
4 Correct 231 ms 531796 KB Output is correct
5 Incorrect 35 ms 257104 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 249348 KB Output is correct
2 Runtime error 1298 ms 1076392 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 247376 KB Output is correct
2 Correct 326 ms 532536 KB Output is correct
3 Correct 448 ms 532972 KB Output is correct
4 Correct 442 ms 533888 KB Output is correct
5 Correct 432 ms 533760 KB Output is correct
6 Correct 474 ms 534068 KB Output is correct
7 Correct 509 ms 533916 KB Output is correct
8 Correct 422 ms 533580 KB Output is correct
9 Correct 406 ms 533688 KB Output is correct
10 Correct 448 ms 533516 KB Output is correct
11 Correct 507 ms 534020 KB Output is correct
12 Correct 608 ms 534052 KB Output is correct
13 Correct 487 ms 533840 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 247376 KB Output is correct
2 Correct 326 ms 532536 KB Output is correct
3 Correct 448 ms 532972 KB Output is correct
4 Correct 442 ms 533888 KB Output is correct
5 Correct 432 ms 533760 KB Output is correct
6 Correct 474 ms 534068 KB Output is correct
7 Correct 509 ms 533916 KB Output is correct
8 Correct 422 ms 533580 KB Output is correct
9 Correct 406 ms 533688 KB Output is correct
10 Correct 448 ms 533516 KB Output is correct
11 Correct 507 ms 534020 KB Output is correct
12 Correct 608 ms 534052 KB Output is correct
13 Correct 487 ms 533840 KB Output is correct
14 Incorrect 34 ms 243280 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 31 ms 247376 KB Output is correct
2 Correct 326 ms 532536 KB Output is correct
3 Correct 448 ms 532972 KB Output is correct
4 Correct 442 ms 533888 KB Output is correct
5 Correct 432 ms 533760 KB Output is correct
6 Correct 474 ms 534068 KB Output is correct
7 Correct 509 ms 533916 KB Output is correct
8 Correct 422 ms 533580 KB Output is correct
9 Correct 406 ms 533688 KB Output is correct
10 Correct 448 ms 533516 KB Output is correct
11 Correct 507 ms 534020 KB Output is correct
12 Correct 608 ms 534052 KB Output is correct
13 Correct 487 ms 533840 KB Output is correct
14 Incorrect 34 ms 243280 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 249348 KB Output is correct
2 Runtime error 1298 ms 1076392 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -