oj.uz

Submission #626398

# Submission time Handle Problem Language Result Execution time Memory
626398 2022-08-11T12:21:00 Z juancarlovieri Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 498104 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long

int n;
vector<signed> s, p, w, l;
pair<int, pair<int, int>> win[400005][25];
pair<int, pair<int, int>> los[400005][25];

void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
  n = N, s = S, p = P, w = W, l = L;
  for (int i = 0; i < n; ++i) {
    win[i][0] = {s[i], {s[i], w[i]}};
    los[i][0] = {s[i] - 1, {p[i], l[i]}};
  }

  for (int j = 1; j < 24; ++j) {
    for (int i = 0; i < n; ++i) {
      if (win[i][j - 1].second.second == n) {
        win[i][j] = win[i][j - 1];
      } else {
        auto lft = win[i][j - 1];
        auto rgt = win[win[i][j - 1].second.second][j - 1];
        int aft = lft.first + lft.second.first;
        win[i][j] = {lft.first + max(0ll, 1ll * rgt.first - aft), {lft.second.first + rgt.second.first, rgt.second.second}};
      }

      if (los[i][j - 1].second.second == n) {
        los[i][j] = los[i][j - 1];
      } else {
        auto lft = los[i][j - 1];
        auto rgt = los[lft.second.second][j - 1];
        int aft = lft.first + lft.second.first;
        los[i][j] = {lft.first - max(0ll, 1ll * aft - rgt.first), {lft.second.first + rgt.second.first, rgt.second.second}};
      }
    }
  }
  return;
}

long long simulate(signed x, signed Z) {
  // int ans = 0;   
  ll z = Z;
  while (x != n) {
    for (int i = 23; i >= 0; --i) {
      if (x == n) break;
      if (win[x][i].first <= z) {
        auto cur = win[x][i];
        x = cur.second.second;
        z += cur.second.first;
      }
    }

    for (int i = 23; i >= 0; --i) {
      if (x == n) break;
      if (los[x][i].first >= z) {
        auto cur = los[x][i];
        x = cur.second.second;
        z += cur.second.first;
      }
    }
  }
  return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 73 ms 62392 KB Output is correct
5 Correct 2 ms 2748 KB Output is correct
6 Correct 73 ms 62268 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 719 ms 496380 KB Output is correct
3 Correct 613 ms 496460 KB Output is correct
4 Correct 623 ms 498104 KB Output is correct
5 Correct 620 ms 498004 KB Output is correct
6 Correct 677 ms 496460 KB Output is correct
7 Correct 622 ms 494672 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 99 ms 63780 KB Output is correct
3 Correct 108 ms 63872 KB Output is correct
4 Correct 95 ms 63296 KB Output is correct
5 Correct 97 ms 63264 KB Output is correct
6 Correct 108 ms 63420 KB Output is correct
7 Correct 113 ms 63548 KB Output is correct
8 Correct 93 ms 63160 KB Output is correct
9 Correct 97 ms 63328 KB Output is correct
10 Correct 94 ms 63040 KB Output is correct
11 Correct 101 ms 63416 KB Output is correct
12 Correct 171 ms 63420 KB Output is correct
13 Correct 181 ms 63432 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 99 ms 63780 KB Output is correct
3 Correct 108 ms 63872 KB Output is correct
4 Correct 95 ms 63296 KB Output is correct
5 Correct 97 ms 63264 KB Output is correct
6 Correct 108 ms 63420 KB Output is correct
7 Correct 113 ms 63548 KB Output is correct
8 Correct 93 ms 63160 KB Output is correct
9 Correct 97 ms 63328 KB Output is correct
10 Correct 94 ms 63040 KB Output is correct
11 Correct 101 ms 63416 KB Output is correct
12 Correct 171 ms 63420 KB Output is correct
13 Correct 181 ms 63432 KB Output is correct
14 Correct 2 ms 1464 KB Output is correct
15 Correct 240 ms 63576 KB Output is correct
16 Correct 109 ms 63780 KB Output is correct
17 Correct 98 ms 63280 KB Output is correct
18 Correct 120 ms 63276 KB Output is correct
19 Correct 119 ms 63420 KB Output is correct
20 Correct 137 ms 63160 KB Output is correct
21 Correct 112 ms 63204 KB Output is correct
22 Execution timed out 7078 ms 63284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 99 ms 63780 KB Output is correct
3 Correct 108 ms 63872 KB Output is correct
4 Correct 95 ms 63296 KB Output is correct
5 Correct 97 ms 63264 KB Output is correct
6 Correct 108 ms 63420 KB Output is correct
7 Correct 113 ms 63548 KB Output is correct
8 Correct 93 ms 63160 KB Output is correct
9 Correct 97 ms 63328 KB Output is correct
10 Correct 94 ms 63040 KB Output is correct
11 Correct 101 ms 63416 KB Output is correct
12 Correct 171 ms 63420 KB Output is correct
13 Correct 181 ms 63432 KB Output is correct
14 Correct 2 ms 1464 KB Output is correct
15 Correct 240 ms 63576 KB Output is correct
16 Correct 109 ms 63780 KB Output is correct
17 Correct 98 ms 63280 KB Output is correct
18 Correct 120 ms 63276 KB Output is correct
19 Correct 119 ms 63420 KB Output is correct
20 Correct 137 ms 63160 KB Output is correct
21 Correct 112 ms 63204 KB Output is correct
22 Execution timed out 7078 ms 63284 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 719 ms 496380 KB Output is correct
3 Correct 613 ms 496460 KB Output is correct
4 Correct 623 ms 498104 KB Output is correct
5 Correct 620 ms 498004 KB Output is correct
6 Correct 677 ms 496460 KB Output is correct
7 Correct 622 ms 494672 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 99 ms 63780 KB Output is correct
10 Correct 108 ms 63872 KB Output is correct
11 Correct 95 ms 63296 KB Output is correct
12 Correct 97 ms 63264 KB Output is correct
13 Correct 108 ms 63420 KB Output is correct
14 Correct 113 ms 63548 KB Output is correct
15 Correct 93 ms 63160 KB Output is correct
16 Correct 97 ms 63328 KB Output is correct
17 Correct 94 ms 63040 KB Output is correct
18 Correct 101 ms 63416 KB Output is correct
19 Correct 171 ms 63420 KB Output is correct
20 Correct 181 ms 63432 KB Output is correct
21 Correct 2 ms 1464 KB Output is correct
22 Correct 240 ms 63576 KB Output is correct
23 Correct 109 ms 63780 KB Output is correct
24 Correct 98 ms 63280 KB Output is correct
25 Correct 120 ms 63276 KB Output is correct
26 Correct 119 ms 63420 KB Output is correct
27 Correct 137 ms 63160 KB Output is correct
28 Correct 112 ms 63204 KB Output is correct
29 Execution timed out 7078 ms 63284 KB Time limit exceeded
30 Halted 0 ms 0 KB -