oj.uz

Submission #887883

# Submission time Handle Problem Language Result Execution time Memory
887883 2023-12-15T12:23:34 Z nguyentunglam Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 1412128 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 4e5 + 10, M = 23;

long long gain[9][M + 1][N];

int can_win[9][M + 1][N];

int go[9][M + 1][N];

int base[20];

int group[10000010];

int s[N], p[N], w[N], l[N];

int n;

mt19937 rng(14978141);

int rnd(int l, int r) {
  return l + rng() % (r - l + 1);
}

void init(int _n, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
  n = _n;

  for(int i = 0; i < n; i++) {
    s[i] = S[i];
    p[i] = P[i];
    w[i] = W[i];
    l[i] = L[i];
  }

  base[0] = 1;
  for(int i = 1; i <= 10; i++) base[i] = base[i - 1] * 8;


  for(int i = 1; i <= 1e7; i++) {
    group[i] = group[i - 1];
    if (i >= base[group[i] + 1]) group[i]++;
  }

  for(int j = 0; j <= 8; j++) {
    for(int i = 0; i < n; i++) {
      if (group[s[i]] < j) {
        go[j][0][i] = w[i];
        gain[j][0][i] = s[i];
        can_win[j][0][i] = 1e9;
      }
      else {
        go[j][0][i] = l[i];
        gain[j][0][i] = p[i];
        can_win[j][0][i] = s[i];
      }
    }
    for(int k = 1; k <= M; k++) for(int i = 0; i < n; i++) {
      int nxt = go[j][k - 1][i];
      if (nxt == n) {
        go[j][k][i] = go[j][k - 1][i];
        gain[j][k][i] = gain[j][k - 1][i];
        can_win[j][k][i] = can_win[j][k - 1][i];
      }
      else {
        go[j][k][i] = go[j][k - 1][nxt];
        gain[j][k][i] = gain[j][k - 1][i] + gain[j][k - 1][nxt];
        long long tmp = 1LL * can_win[j][k - 1][nxt] - gain[j][k - 1][i];
        tmp = max(tmp, 0LL);
        can_win[j][k][i] = min(can_win[j][k - 1][i], (int) tmp);
      }
    }
  }

	return;
}

long long simulate(int x, int _z) {
  long long z = _z;
  while (x != n) {
    int j = z >= 1e7 ? 8 : group[z];
    for(int k = M; k >= 0; k--) {
      if (z >= can_win[j][k][x]) continue;
      z += gain[j][k][x];
      x = go[j][k][x];
      if (x == n) return z;
    }
    if (z >= s[x]) {
      z += s[x];
      x = w[x];
    }
    else {
      z += p[x];
      x = l[x];
    }
  }
  return z;
}


#ifdef ngu
int32_t main() {

  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);

  int n, q; cin >> n >> q;

  vector<int> s(n), p(n), w(n), l(n);

  for(int i = 0; i < n; i++) cin >> s[i];
  for(int i = 0; i < n; i++) cin >> p[i];
  for(int i = 0; i < n; i++) cin >> w[i];
  for(int i = 0; i < n; i++) cin >> l[i];

  init(n, s, p, w, l);

  while (q--) {
    int x, z; cin >> x >> z;
    cout << simulate(x, z) << endl;
  }
}
#endif // ngu

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 806580 KB Output is correct
2 Correct 120 ms 1028884 KB Output is correct
3 Correct 148 ms 1141532 KB Output is correct
4 Correct 183 ms 1238788 KB Output is correct
5 Correct 133 ms 1167952 KB Output is correct
6 Correct 177 ms 1246032 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1163856 KB Output is correct
2 Correct 557 ms 1411604 KB Output is correct
3 Correct 503 ms 1412128 KB Output is correct
4 Correct 485 ms 1411672 KB Output is correct
5 Correct 550 ms 1411672 KB Output is correct
6 Correct 622 ms 1411668 KB Output is correct
7 Correct 523 ms 1411896 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 1163820 KB Output is correct
2 Correct 207 ms 1250528 KB Output is correct
3 Execution timed out 7027 ms 1250388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 1163820 KB Output is correct
2 Correct 207 ms 1250528 KB Output is correct
3 Execution timed out 7027 ms 1250388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 1163820 KB Output is correct
2 Correct 207 ms 1250528 KB Output is correct
3 Execution timed out 7027 ms 1250388 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 1163856 KB Output is correct
2 Correct 557 ms 1411604 KB Output is correct
3 Correct 503 ms 1412128 KB Output is correct
4 Correct 485 ms 1411672 KB Output is correct
5 Correct 550 ms 1411672 KB Output is correct
6 Correct 622 ms 1411668 KB Output is correct
7 Correct 523 ms 1411896 KB Output is correct
8 Correct 133 ms 1163820 KB Output is correct
9 Correct 207 ms 1250528 KB Output is correct
10 Execution timed out 7027 ms 1250388 KB Time limit exceeded
11 Halted 0 ms 0 KB -