oj.uz

Submission #879792

# Submission time Handle Problem Language Result Execution time Memory
879792 2023-11-28T06:52:35 Z abcvuitunggio Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 1340568 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int sz=24;
int nxt[400001][sz][5];
long long mx[400001][sz][5],mn[400001][sz][5],sum[400001][sz][5];
vector <int> S,P,ve={1,57,3249,185193};
void init(int n, vector <int> s, vector <int> p, vector <int> w, vector <int> l){
    S=s;
    P=p;
    memset(nxt,-1,sizeof(nxt));
    for (int i=0;i<n;i++){
        for (int j=0;j<4;j++)
            if (s[i]<=ve[j]){
                nxt[i][0][j]=w[i];
                sum[i][0][j]=s[i];
            }
            else{
                nxt[i][0][j]=l[i];
                sum[i][0][j]=p[i];
            }
        nxt[i][0][4]=w[i];
        for (int j=0;j<5;j++)
            mx[i][0][j]=mn[i][0][j]=s[i];
        sum[i][0][4]=s[i];
    }
    for (int j=1;j<sz;j++){
        for (int i=0;i<n;i++)
            for (int k=0;k<5;k++){
                if (nxt[i][j-1][k]==-1)
                    continue;
                int u=nxt[i][j-1][k];
                nxt[i][j][k]=nxt[u][j-1][k];
                mx[i][j][k]=max(mx[i][j-1][k],mx[u][j-1][k]-sum[i][j-1][k]);
                mn[i][j][k]=min(mn[i][j-1][k],mn[u][j-1][k]-sum[i][j-1][k]);
                sum[i][j][k]=sum[i][j-1][k]+sum[u][j-1][k];
            }
    }
}
long long simulate(int x, int Z){
    int b=0;
    long long z=Z;
    while (true){
        if (nxt[x][0][0]==-1)
            return z;
        int j=(b?upper_bound(ve.begin(),ve.end(),z)-ve.begin()-1:4);
        for (int i=sz-1;i>=0;i--)
            if (nxt[x][i][j]!=-1)
                if ((b&&z<mn[x][i][j])||(!b&&z>=mx[x][i][j])){
                    z+=sum[x][i][j];
                    x=nxt[x][i][j];
                }
        b^=1;
    }
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 192848 KB Output is correct
2 Correct 22 ms 192852 KB Output is correct
3 Correct 27 ms 197264 KB Output is correct
4 Correct 230 ms 335600 KB Output is correct
5 Correct 24 ms 197460 KB Output is correct
6 Correct 172 ms 335452 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 195152 KB Output is correct
2 Correct 2620 ms 1331948 KB Output is correct
3 Correct 2190 ms 1338840 KB Output is correct
4 Correct 2025 ms 1340380 KB Output is correct
5 Correct 1730 ms 1340568 KB Output is correct
6 Correct 2106 ms 1338964 KB Output is correct
7 Correct 2029 ms 1337056 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 195156 KB Output is correct
2 Correct 228 ms 336936 KB Output is correct
3 Correct 243 ms 336960 KB Output is correct
4 Correct 209 ms 336468 KB Output is correct
5 Correct 187 ms 336320 KB Output is correct
6 Correct 226 ms 336416 KB Output is correct
7 Correct 225 ms 336468 KB Output is correct
8 Correct 215 ms 336340 KB Output is correct
9 Correct 147 ms 336464 KB Output is correct
10 Correct 210 ms 336408 KB Output is correct
11 Correct 250 ms 336824 KB Output is correct
12 Correct 342 ms 336704 KB Output is correct
13 Correct 272 ms 336468 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 195156 KB Output is correct
2 Correct 228 ms 336936 KB Output is correct
3 Correct 243 ms 336960 KB Output is correct
4 Correct 209 ms 336468 KB Output is correct
5 Correct 187 ms 336320 KB Output is correct
6 Correct 226 ms 336416 KB Output is correct
7 Correct 225 ms 336468 KB Output is correct
8 Correct 215 ms 336340 KB Output is correct
9 Correct 147 ms 336464 KB Output is correct
10 Correct 210 ms 336408 KB Output is correct
11 Correct 250 ms 336824 KB Output is correct
12 Correct 342 ms 336704 KB Output is correct
13 Correct 272 ms 336468 KB Output is correct
14 Correct 24 ms 195164 KB Output is correct
15 Correct 333 ms 336708 KB Output is correct
16 Correct 234 ms 336980 KB Output is correct
17 Correct 225 ms 336448 KB Output is correct
18 Correct 242 ms 336468 KB Output is correct
19 Correct 234 ms 336716 KB Output is correct
20 Correct 262 ms 336212 KB Output is correct
21 Correct 246 ms 336724 KB Output is correct
22 Execution timed out 7051 ms 336468 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 195156 KB Output is correct
2 Correct 228 ms 336936 KB Output is correct
3 Correct 243 ms 336960 KB Output is correct
4 Correct 209 ms 336468 KB Output is correct
5 Correct 187 ms 336320 KB Output is correct
6 Correct 226 ms 336416 KB Output is correct
7 Correct 225 ms 336468 KB Output is correct
8 Correct 215 ms 336340 KB Output is correct
9 Correct 147 ms 336464 KB Output is correct
10 Correct 210 ms 336408 KB Output is correct
11 Correct 250 ms 336824 KB Output is correct
12 Correct 342 ms 336704 KB Output is correct
13 Correct 272 ms 336468 KB Output is correct
14 Correct 24 ms 195164 KB Output is correct
15 Correct 333 ms 336708 KB Output is correct
16 Correct 234 ms 336980 KB Output is correct
17 Correct 225 ms 336448 KB Output is correct
18 Correct 242 ms 336468 KB Output is correct
19 Correct 234 ms 336716 KB Output is correct
20 Correct 262 ms 336212 KB Output is correct
21 Correct 246 ms 336724 KB Output is correct
22 Execution timed out 7051 ms 336468 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 195152 KB Output is correct
2 Correct 2620 ms 1331948 KB Output is correct
3 Correct 2190 ms 1338840 KB Output is correct
4 Correct 2025 ms 1340380 KB Output is correct
5 Correct 1730 ms 1340568 KB Output is correct
6 Correct 2106 ms 1338964 KB Output is correct
7 Correct 2029 ms 1337056 KB Output is correct
8 Correct 24 ms 195156 KB Output is correct
9 Correct 228 ms 336936 KB Output is correct
10 Correct 243 ms 336960 KB Output is correct
11 Correct 209 ms 336468 KB Output is correct
12 Correct 187 ms 336320 KB Output is correct
13 Correct 226 ms 336416 KB Output is correct
14 Correct 225 ms 336468 KB Output is correct
15 Correct 215 ms 336340 KB Output is correct
16 Correct 147 ms 336464 KB Output is correct
17 Correct 210 ms 336408 KB Output is correct
18 Correct 250 ms 336824 KB Output is correct
19 Correct 342 ms 336704 KB Output is correct
20 Correct 272 ms 336468 KB Output is correct
21 Correct 24 ms 195164 KB Output is correct
22 Correct 333 ms 336708 KB Output is correct
23 Correct 234 ms 336980 KB Output is correct
24 Correct 225 ms 336448 KB Output is correct
25 Correct 242 ms 336468 KB Output is correct
26 Correct 234 ms 336716 KB Output is correct
27 Correct 262 ms 336212 KB Output is correct
28 Correct 246 ms 336724 KB Output is correct
29 Execution timed out 7051 ms 336468 KB Time limit exceeded
30 Halted 0 ms 0 KB -