oj.uz

Submission #929123

# Submission time Handle Problem Language Result Execution time Memory
929123 2024-02-17T18:20:55 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
11 / 100
 392 ms 497824 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int base=14,sz=7;
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=0;k<sz;k++){
                if (nxt[j-1][i][k]==-1)
                    continue;
                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=23;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 7 is above array bounds of 'int [7]' [-Warray-bounds]
   26 |         nxt[0][i][sz]=w[i];
      |         ~~~~~~~~~~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 360936 KB Output is correct
2 Correct 39 ms 361032 KB Output is correct
3 Correct 42 ms 365376 KB Output is correct
4 Correct 98 ms 496960 KB Output is correct
5 Correct 41 ms 365388 KB Output is correct
6 Correct 90 ms 496988 KB Output is correct

Subtask #2
0.0 / 26.0

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

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 363264 KB Output is correct
2 Correct 145 ms 497584 KB Output is correct
3 Correct 143 ms 497744 KB Output is correct
4 Correct 117 ms 497700 KB Output is correct
5 Correct 110 ms 497744 KB Output is correct
6 Correct 131 ms 497640 KB Output is correct
7 Correct 123 ms 497748 KB Output is correct
8 Correct 113 ms 497816 KB Output is correct
9 Correct 121 ms 497732 KB Output is correct
10 Correct 132 ms 497744 KB Output is correct
11 Correct 141 ms 430108 KB Output is correct
12 Incorrect 392 ms 497824 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 363264 KB Output is correct
2 Correct 145 ms 497584 KB Output is correct
3 Correct 143 ms 497744 KB Output is correct
4 Correct 117 ms 497700 KB Output is correct
5 Correct 110 ms 497744 KB Output is correct
6 Correct 131 ms 497640 KB Output is correct
7 Correct 123 ms 497748 KB Output is correct
8 Correct 113 ms 497816 KB Output is correct
9 Correct 121 ms 497732 KB Output is correct
10 Correct 132 ms 497744 KB Output is correct
11 Correct 141 ms 430108 KB Output is correct
12 Incorrect 392 ms 497824 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 363264 KB Output is correct
2 Correct 145 ms 497584 KB Output is correct
3 Correct 143 ms 497744 KB Output is correct
4 Correct 117 ms 497700 KB Output is correct
5 Correct 110 ms 497744 KB Output is correct
6 Correct 131 ms 497640 KB Output is correct
7 Correct 123 ms 497748 KB Output is correct
8 Correct 113 ms 497816 KB Output is correct
9 Correct 121 ms 497732 KB Output is correct
10 Correct 132 ms 497744 KB Output is correct
11 Correct 141 ms 430108 KB Output is correct
12 Incorrect 392 ms 497824 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

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