oj.uz

Submission #929129

# Submission time Handle Problem Language Result Execution time Memory
929129 2024-02-17T18:28:04 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 1590924 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=6,sz=10;
const long long INF=1e18;
int N,nxt[24][400001][sz];
long long mn[24][400001][sz],sum[24][400001][sz];
vector <int> S,P,W,L,ve={1};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    N=n,S=s,P=p,W=w,L=l;
    for (int i=1;i<sz;i++)
        ve.push_back(ve.back()*base);
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        for (int j=0;j<sz;j++)
            if (s[i]<=ve[j]){
                nxt[0][i][j]=w[i];
                sum[0][i][j]=s[i];
                mn[0][i][j]=INF;
            }
            else{
                nxt[0][i][j]=l[i];
                sum[0][i][j]=p[i];
                mn[0][i][j]=s[i];
            }
        nxt[0][i][sz]=w[i];
    }
    for (int j=1;j<24;j++){
        for (int i=0;i<n;i++)
            for (int k=sz-1;k>=0;k--){
                if (nxt[j-1][i][k]==-1)
                    break;
                int u=nxt[j-1][i][k];
                nxt[j][i][k]=nxt[j-1][u][k];
                mn[j][i][k]=min(mn[j-1][i][k],mn[j-1][u][k]-sum[j-1][i][k]);
                sum[j][i][k]=sum[j-1][i][k]+sum[j-1][u][k];
            }
    }
}
long long simulate(int x, int Z){
    int cur=0;
    long long z=Z;
    while (cur<sz){
        while (cur<sz&&ve[cur]<=z)
            cur++;
        int j=cur-1;
        for (int i=23;i>=0;i--)
            if (nxt[i][x][j]!=-1&&z<mn[i][x][j]){
                z+=sum[i][x][j];
                x=nxt[i][x][j];
            }
        if (x==N)
            break;
        if (z<S[x]){
            z+=P[x];
            x=L[x];
        }
        else{
            z+=S[x];
            x=W[x];
        }
    }
    int j=cur-1;
    for (int i=18;i>=0;i--)
        if (nxt[i][x][j]!=-1){
            z+=sum[i][x][j];
            x=nxt[i][x][j];
        }
    return z;
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:26:21: warning: array subscript 10 is above array bounds of 'int [10]' [-Warray-bounds]
   26 |         nxt[0][i][sz]=w[i];
      |         ~~~~~~~~~~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 382804 KB Output is correct
2 Correct 44 ms 391024 KB Output is correct
3 Correct 47 ms 401996 KB Output is correct
4 Correct 103 ms 451024 KB Output is correct
5 Correct 46 ms 401552 KB Output is correct
6 Correct 85 ms 451156 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 399444 KB Output is correct
2 Correct 667 ms 1548092 KB Output is correct
3 Correct 610 ms 1590924 KB Output is correct
4 Correct 594 ms 1590764 KB Output is correct
5 Correct 442 ms 773972 KB Output is correct
6 Correct 715 ms 1548032 KB Output is correct
7 Correct 548 ms 1590844 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 395348 KB Output is correct
2 Correct 145 ms 451920 KB Output is correct
3 Correct 146 ms 566920 KB Output is correct
4 Correct 126 ms 575056 KB Output is correct
5 Correct 123 ms 566868 KB Output is correct
6 Correct 5402 ms 451920 KB Output is correct
7 Execution timed out 7014 ms 449936 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 395348 KB Output is correct
2 Correct 145 ms 451920 KB Output is correct
3 Correct 146 ms 566920 KB Output is correct
4 Correct 126 ms 575056 KB Output is correct
5 Correct 123 ms 566868 KB Output is correct
6 Correct 5402 ms 451920 KB Output is correct
7 Execution timed out 7014 ms 449936 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 395348 KB Output is correct
2 Correct 145 ms 451920 KB Output is correct
3 Correct 146 ms 566920 KB Output is correct
4 Correct 126 ms 575056 KB Output is correct
5 Correct 123 ms 566868 KB Output is correct
6 Correct 5402 ms 451920 KB Output is correct
7 Execution timed out 7014 ms 449936 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 399444 KB Output is correct
2 Correct 667 ms 1548092 KB Output is correct
3 Correct 610 ms 1590924 KB Output is correct
4 Correct 594 ms 1590764 KB Output is correct
5 Correct 442 ms 773972 KB Output is correct
6 Correct 715 ms 1548032 KB Output is correct
7 Correct 548 ms 1590844 KB Output is correct
8 Correct 45 ms 395348 KB Output is correct
9 Correct 145 ms 451920 KB Output is correct
10 Correct 146 ms 566920 KB Output is correct
11 Correct 126 ms 575056 KB Output is correct
12 Correct 123 ms 566868 KB Output is correct
13 Correct 5402 ms 451920 KB Output is correct
14 Execution timed out 7014 ms 449936 KB Time limit exceeded
15 Halted 0 ms 0 KB -