oj.uz

Submission #961801

# Submission time Handle Problem Language Result Execution time Memory
961801 2024-04-12T13:21:51 Z Warinchai Dungeons Game (IOI21_dungeons) C++17
63 / 100
 3120 ms 1208876 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[26][26][50005];
long long 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;
long long 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;
        if(i==0)st=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){
        assert(pow > (1<<(lv-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:49:15: warning: unused variable 'c' [-Wunused-variable]
   49 |     long long c=0,lv=0;
      |               ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 444496 KB Output is correct
2 Correct 48 ms 442708 KB Output is correct
3 Correct 58 ms 457296 KB Output is correct
4 Correct 249 ms 665208 KB Output is correct
5 Correct 64 ms 476756 KB Output is correct
6 Correct 232 ms 665132 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 472712 KB Output is correct
2 Runtime error 1474 ms 1208876 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 61 ms 482644 KB Output is correct
2 Correct 497 ms 666180 KB Output is correct
3 Correct 1187 ms 666088 KB Output is correct
4 Correct 1025 ms 665732 KB Output is correct
5 Correct 1000 ms 665764 KB Output is correct
6 Correct 1457 ms 665852 KB Output is correct
7 Correct 1656 ms 665776 KB Output is correct
8 Correct 1185 ms 665728 KB Output is correct
9 Correct 390 ms 665936 KB Output is correct
10 Correct 1087 ms 665520 KB Output is correct
11 Correct 1288 ms 665684 KB Output is correct
12 Correct 2996 ms 665752 KB Output is correct
13 Correct 3120 ms 665748 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 482644 KB Output is correct
2 Correct 497 ms 666180 KB Output is correct
3 Correct 1187 ms 666088 KB Output is correct
4 Correct 1025 ms 665732 KB Output is correct
5 Correct 1000 ms 665764 KB Output is correct
6 Correct 1457 ms 665852 KB Output is correct
7 Correct 1656 ms 665776 KB Output is correct
8 Correct 1185 ms 665728 KB Output is correct
9 Correct 390 ms 665936 KB Output is correct
10 Correct 1087 ms 665520 KB Output is correct
11 Correct 1288 ms 665684 KB Output is correct
12 Correct 2996 ms 665752 KB Output is correct
13 Correct 3120 ms 665748 KB Output is correct
14 Correct 72 ms 510544 KB Output is correct
15 Correct 814 ms 666128 KB Output is correct
16 Correct 479 ms 666576 KB Output is correct
17 Correct 1248 ms 666056 KB Output is correct
18 Correct 1285 ms 666076 KB Output is correct
19 Correct 1263 ms 666324 KB Output is correct
20 Correct 1249 ms 665884 KB Output is correct
21 Correct 1426 ms 666172 KB Output is correct
22 Correct 1064 ms 666420 KB Output is correct
23 Correct 1464 ms 666196 KB Output is correct
24 Correct 1966 ms 666196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 482644 KB Output is correct
2 Correct 497 ms 666180 KB Output is correct
3 Correct 1187 ms 666088 KB Output is correct
4 Correct 1025 ms 665732 KB Output is correct
5 Correct 1000 ms 665764 KB Output is correct
6 Correct 1457 ms 665852 KB Output is correct
7 Correct 1656 ms 665776 KB Output is correct
8 Correct 1185 ms 665728 KB Output is correct
9 Correct 390 ms 665936 KB Output is correct
10 Correct 1087 ms 665520 KB Output is correct
11 Correct 1288 ms 665684 KB Output is correct
12 Correct 2996 ms 665752 KB Output is correct
13 Correct 3120 ms 665748 KB Output is correct
14 Correct 72 ms 510544 KB Output is correct
15 Correct 814 ms 666128 KB Output is correct
16 Correct 479 ms 666576 KB Output is correct
17 Correct 1248 ms 666056 KB Output is correct
18 Correct 1285 ms 666076 KB Output is correct
19 Correct 1263 ms 666324 KB Output is correct
20 Correct 1249 ms 665884 KB Output is correct
21 Correct 1426 ms 666172 KB Output is correct
22 Correct 1064 ms 666420 KB Output is correct
23 Correct 1464 ms 666196 KB Output is correct
24 Correct 1966 ms 666196 KB Output is correct
25 Correct 256 ms 665628 KB Output is correct
26 Correct 534 ms 666692 KB Output is correct
27 Correct 567 ms 666056 KB Output is correct
28 Correct 607 ms 666188 KB Output is correct
29 Correct 541 ms 666428 KB Output is correct
30 Correct 1311 ms 666212 KB Output is correct
31 Correct 1413 ms 665932 KB Output is correct
32 Correct 1506 ms 666144 KB Output is correct
33 Correct 1206 ms 666328 KB Output is correct
34 Correct 1672 ms 666196 KB Output is correct
35 Correct 1433 ms 666352 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 472712 KB Output is correct
2 Runtime error 1474 ms 1208876 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -