oj.uz

Submission #990930

# Submission time Handle Problem Language Result Execution time Memory
990930 2024-05-31T20:21:28 Z AdamGS Dungeons Game (IOI21_dungeons) C++17
63 / 100
 2591 ms 701376 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e4+7, LG=24;
ll nxt[LIM][LG][LG], sum[LIM][LG][LG], ile[LIM][LG][LG], nxt2[LIM][LG], sum2[LIM][LG], S[LIM], P[LIM], W[LIM], L[LIM], n;
void init(int _n, vector<int>_s, vector<int>_p, vector<int>_w, vector<int>_l) {
  n=_n;
  rep(i, n) {
    S[i]=_s[i];
    P[i]=_p[i];
    W[i]=_w[i];
    L[i]=_l[i];
  }
  rep(i, LG) {
    nxt[n][i][0]=n;
    rep(j, n) {
      if(S[j]>=(1<<i)) {
        nxt[j][i][0]=L[j];
        sum[j][i][0]=P[j];
        ile[j][i][0]=min(S[j], (1<<(i+1))-P[j]);
      } else {
        nxt[j][i][0]=W[j];
        sum[j][i][0]=S[j];
        ile[j][i][0]=(1<<(i+1))-S[j];
      }
    }
    for(int l=1; l<LG; ++l) {
      rep(j, n+1) {
        nxt[j][i][l]=nxt[nxt[j][i][l-1]][i][l-1];
        sum[j][i][l]=sum[j][i][l-1]+sum[nxt[j][i][l-1]][i][l-1];
        ile[j][i][l]=min(ile[j][i][l-1], ile[nxt[j][i][l-1]][i][l-1]-sum[j][i][l-1]);
      }
    }
  }
  nxt2[n][0]=n;
  rep(i, n) {
    nxt2[i][0]=W[i];
    sum2[i][0]=S[i];
  }
  for(int j=1; j<LG; ++j) {
    rep(i, n+1) {
      nxt2[i][j]=nxt2[nxt2[i][j-1]][j-1];
      sum2[i][j]=sum2[nxt2[i][j-1]][j-1]+sum2[i][j-1];
    }
  }
  return;
}
ll simulate(int x, int _z) {
  ll z=_z;
  rep(i, LG) if(z<(1ll<<(ll)(i+1))) {
    for(int j=LG-1; j>=0; --j) if(nxt[x][i][j]<n && ile[x][i][j]>z) {
      z+=sum[x][i][j];
      x=nxt[x][i][j];
    }
    if(z>=S[x]) {
      z+=S[x];
      x=W[x];
    } else {
      z+=P[x];
      x=L[x];
    }
    if(x==n) return z;
  }
  for(int i=LG-1; i>=0; --i) if(nxt2[x][i]<n) {
    z+=sum2[x][i];
    x=nxt2[x][i];
  }
  z+=sum2[x][0];
  x=nxt2[x][0];
  return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 18 ms 39548 KB Output is correct
4 Correct 881 ms 699572 KB Output is correct
5 Correct 21 ms 39516 KB Output is correct
6 Correct 938 ms 699432 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Runtime error 114 ms 33472 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 13 ms 24924 KB Output is correct
2 Correct 991 ms 701012 KB Output is correct
3 Correct 834 ms 701376 KB Output is correct
4 Correct 890 ms 700500 KB Output is correct
5 Correct 861 ms 700372 KB Output is correct
6 Correct 932 ms 700824 KB Output is correct
7 Correct 950 ms 700752 KB Output is correct
8 Correct 1234 ms 700500 KB Output is correct
9 Correct 834 ms 700500 KB Output is correct
10 Correct 1216 ms 700244 KB Output is correct
11 Correct 1304 ms 700760 KB Output is correct
12 Correct 2560 ms 700836 KB Output is correct
13 Correct 2591 ms 700756 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24924 KB Output is correct
2 Correct 991 ms 701012 KB Output is correct
3 Correct 834 ms 701376 KB Output is correct
4 Correct 890 ms 700500 KB Output is correct
5 Correct 861 ms 700372 KB Output is correct
6 Correct 932 ms 700824 KB Output is correct
7 Correct 950 ms 700752 KB Output is correct
8 Correct 1234 ms 700500 KB Output is correct
9 Correct 834 ms 700500 KB Output is correct
10 Correct 1216 ms 700244 KB Output is correct
11 Correct 1304 ms 700760 KB Output is correct
12 Correct 2560 ms 700836 KB Output is correct
13 Correct 2591 ms 700756 KB Output is correct
14 Correct 11 ms 24924 KB Output is correct
15 Correct 826 ms 700992 KB Output is correct
16 Correct 879 ms 701016 KB Output is correct
17 Correct 880 ms 700496 KB Output is correct
18 Correct 880 ms 700740 KB Output is correct
19 Correct 917 ms 700756 KB Output is correct
20 Correct 1037 ms 700376 KB Output is correct
21 Correct 1081 ms 700500 KB Output is correct
22 Correct 1124 ms 700496 KB Output is correct
23 Correct 1624 ms 700760 KB Output is correct
24 Correct 1695 ms 700760 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24924 KB Output is correct
2 Correct 991 ms 701012 KB Output is correct
3 Correct 834 ms 701376 KB Output is correct
4 Correct 890 ms 700500 KB Output is correct
5 Correct 861 ms 700372 KB Output is correct
6 Correct 932 ms 700824 KB Output is correct
7 Correct 950 ms 700752 KB Output is correct
8 Correct 1234 ms 700500 KB Output is correct
9 Correct 834 ms 700500 KB Output is correct
10 Correct 1216 ms 700244 KB Output is correct
11 Correct 1304 ms 700760 KB Output is correct
12 Correct 2560 ms 700836 KB Output is correct
13 Correct 2591 ms 700756 KB Output is correct
14 Correct 11 ms 24924 KB Output is correct
15 Correct 826 ms 700992 KB Output is correct
16 Correct 879 ms 701016 KB Output is correct
17 Correct 880 ms 700496 KB Output is correct
18 Correct 880 ms 700740 KB Output is correct
19 Correct 917 ms 700756 KB Output is correct
20 Correct 1037 ms 700376 KB Output is correct
21 Correct 1081 ms 700500 KB Output is correct
22 Correct 1124 ms 700496 KB Output is correct
23 Correct 1624 ms 700760 KB Output is correct
24 Correct 1695 ms 700760 KB Output is correct
25 Correct 812 ms 699988 KB Output is correct
26 Correct 851 ms 701016 KB Output is correct
27 Correct 797 ms 700496 KB Output is correct
28 Correct 901 ms 700496 KB Output is correct
29 Correct 866 ms 701012 KB Output is correct
30 Correct 1136 ms 700588 KB Output is correct
31 Correct 1213 ms 700496 KB Output is correct
32 Correct 1311 ms 700500 KB Output is correct
33 Correct 1093 ms 700496 KB Output is correct
34 Correct 1294 ms 700500 KB Output is correct
35 Correct 1091 ms 700496 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Runtime error 114 ms 33472 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -