oj.uz

Submission #961563

# Submission time Handle Problem Language Result Execution time Memory
961563 2024-04-12T08:11:04 Z Warinchai Dungeons Game (IOI21_dungeons) C++17
13 / 100
 1103 ms 1083328 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;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:48:15: warning: unused variable 'c' [-Wunused-variable]
   48 |     long long c=0,lv=0;
      |               ^

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 527576 KB Output is correct
2 Correct 55 ms 527704 KB Output is correct
3 Correct 58 ms 527952 KB Output is correct
4 Correct 138 ms 531800 KB Output is correct
5 Incorrect 59 ms 527824 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 56 ms 527700 KB Output is correct
2 Runtime error 1103 ms 1083328 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 58 ms 527864 KB Output is correct
2 Correct 244 ms 532740 KB Output is correct
3 Correct 572 ms 532708 KB Output is correct
4 Correct 585 ms 532564 KB Output is correct
5 Correct 576 ms 532616 KB Output is correct
6 Correct 608 ms 532564 KB Output is correct
7 Correct 610 ms 532564 KB Output is correct
8 Correct 577 ms 532588 KB Output is correct
9 Correct 216 ms 532548 KB Output is correct
10 Correct 580 ms 532544 KB Output is correct
11 Correct 630 ms 532532 KB Output is correct
12 Correct 731 ms 532668 KB Output is correct
13 Correct 659 ms 532692 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 527864 KB Output is correct
2 Correct 244 ms 532740 KB Output is correct
3 Correct 572 ms 532708 KB Output is correct
4 Correct 585 ms 532564 KB Output is correct
5 Correct 576 ms 532616 KB Output is correct
6 Correct 608 ms 532564 KB Output is correct
7 Correct 610 ms 532564 KB Output is correct
8 Correct 577 ms 532588 KB Output is correct
9 Correct 216 ms 532548 KB Output is correct
10 Correct 580 ms 532544 KB Output is correct
11 Correct 630 ms 532532 KB Output is correct
12 Correct 731 ms 532668 KB Output is correct
13 Correct 659 ms 532692 KB Output is correct
14 Correct 56 ms 527708 KB Output is correct
15 Incorrect 301 ms 534216 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 527864 KB Output is correct
2 Correct 244 ms 532740 KB Output is correct
3 Correct 572 ms 532708 KB Output is correct
4 Correct 585 ms 532564 KB Output is correct
5 Correct 576 ms 532616 KB Output is correct
6 Correct 608 ms 532564 KB Output is correct
7 Correct 610 ms 532564 KB Output is correct
8 Correct 577 ms 532588 KB Output is correct
9 Correct 216 ms 532548 KB Output is correct
10 Correct 580 ms 532544 KB Output is correct
11 Correct 630 ms 532532 KB Output is correct
12 Correct 731 ms 532668 KB Output is correct
13 Correct 659 ms 532692 KB Output is correct
14 Correct 56 ms 527708 KB Output is correct
15 Incorrect 301 ms 534216 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 527700 KB Output is correct
2 Runtime error 1103 ms 1083328 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -