oj.uz

Submission #887882

# Submission time Handle Problem Language Result Execution time Memory
887882 2023-12-15T12:20:07 Z nguyentunglam Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 1082188 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;

int 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;

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];
        can_win[j][k][i] = min(can_win[j][k - 1][i], can_win[j][k - 1][nxt] - gain[j][k - 1][i]);
      }
    }
  }

	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 295 ms 666876 KB Output is correct
2 Correct 96 ms 728292 KB Output is correct
3 Correct 108 ms 788788 KB Output is correct
4 Correct 147 ms 852820 KB Output is correct
5 Correct 102 ms 821344 KB Output is correct
6 Correct 155 ms 852808 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 820764 KB Output is correct
2 Correct 529 ms 1080144 KB Output is correct
3 Correct 513 ms 1080488 KB Output is correct
4 Correct 510 ms 1082188 KB Output is correct
5 Correct 483 ms 1081944 KB Output is correct
6 Correct 549 ms 1080376 KB Output is correct
7 Correct 485 ms 1078668 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1059156 KB Output is correct
2 Correct 196 ms 1063432 KB Output is correct
3 Execution timed out 7101 ms 1063132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1059156 KB Output is correct
2 Correct 196 ms 1063432 KB Output is correct
3 Execution timed out 7101 ms 1063132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1059156 KB Output is correct
2 Correct 196 ms 1063432 KB Output is correct
3 Execution timed out 7101 ms 1063132 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 820764 KB Output is correct
2 Correct 529 ms 1080144 KB Output is correct
3 Correct 513 ms 1080488 KB Output is correct
4 Correct 510 ms 1082188 KB Output is correct
5 Correct 483 ms 1081944 KB Output is correct
6 Correct 549 ms 1080376 KB Output is correct
7 Correct 485 ms 1078668 KB Output is correct
8 Correct 124 ms 1059156 KB Output is correct
9 Correct 196 ms 1063432 KB Output is correct
10 Execution timed out 7101 ms 1063132 KB Time limit exceeded
11 Halted 0 ms 0 KB -