oj.uz

Submission #443097

# Submission time Handle Problem Language Result Execution time Memory
443097 2021-07-09T16:12:12 Z ltf0501 Dungeons Game (IOI21_dungeons) C++17
25 / 100
 294 ms 154388 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int kN = 4e5 + 10;
const int kC = 25;
// subtask 1, 2, 3
int n;
vector<int> s, p, w, l;
vector<int> uni_s;
long long suf[kN];
int climb[6][kC][kN], MAX; // 0: win, 1: lose
long long max_pow[6][kC][kN], gained_pow[6][kC][kN];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
  n = _n, s = _s, p = _p, w = _w, l = _l;
  w.push_back(n);
  
  for(int i = n - 1; i >= 0; i--) suf[i] = s[i] + suf[w[i]], MAX = max(MAX, s[i]);
  for(int i = 0; i < n; i++) uni_s.push_back(s[i]);
  uni_s.push_back(0);

  sort(uni_s.begin(), uni_s.end());
  uni_s.resize(unique(uni_s.begin(), uni_s.end()) - uni_s.begin());
  int m = int(uni_s.size());
  assert(m <= 6);
  auto get_id = [&](int x) {
    return int(lower_bound(uni_s.begin(), uni_s.end(), x) - uni_s.begin());
  };

  for(int i = 0; i < n; i++) {
    int id = get_id(s[i]);
    for(int j = 0; j < m; j++) { 
      if(j >= id) { // dp[j][][] power at least uni_s[j]
        climb[j][0][i] = w[i];
        max_pow[j][0][i] = MAX;
        gained_pow[j][0][i] = s[i];
      }
      else {
        climb[j][0][i] = l[i];
        max_pow[j][0][i] = s[i] - 1;
        gained_pow[j][0][i] = p[i];
      }
    }
  }

  for(int j = 0; j < m; j++) {
    climb[j][0][n] = n;
    max_pow[j][0][n] = MAX;
    gained_pow[j][0][n] = 0;
  }

  for(int j = 1; j < kC; j++) {
    for(int i = 0; i <= n; i++) {
      for(int o = 0; o < m; o++) {
        climb[o][j][i] = climb[o][j - 1][climb[o][j - 1][i]];
        max_pow[o][j][i] = min(max_pow[o][j - 1][i], max_pow[o][j - 1][climb[o][j - 1][i]] - gained_pow[o][j - 1][i]);
        gained_pow[o][j][i] = gained_pow[o][j - 1][i] + gained_pow[o][j - 1][climb[o][j - 1][i]];
      }
    }
  }

	return;
}

long long simulate(int x, int z) {
  long long res = z;
  while(x < n && res < MAX) {
    int id = upper_bound(uni_s.begin(), uni_s.end(), res) - uni_s.begin() - 1;
    assert(id != -1);
    for(int j = kC - 1; j >= 0; j--) {
      if(res > max_pow[id][j][x]) continue;
      res += gained_pow[id][j][x], x = climb[id][j][x];
    }
    if(x == n) break;
    //cerr << "x = " << x << ", pow = " << res << '\n';
    res += s[x], x = w[x];
  }

  res += suf[x];
  //cerr << "Finish\n";
  return res;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Runtime error 42 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 99 ms 54324 KB Output is correct
3 Correct 98 ms 54340 KB Output is correct
4 Correct 81 ms 54272 KB Output is correct
5 Correct 77 ms 54280 KB Output is correct
6 Correct 123 ms 54328 KB Output is correct
7 Correct 121 ms 54316 KB Output is correct
8 Correct 88 ms 54316 KB Output is correct
9 Correct 85 ms 54232 KB Output is correct
10 Correct 77 ms 54244 KB Output is correct
11 Correct 91 ms 54240 KB Output is correct
12 Correct 181 ms 54312 KB Output is correct
13 Correct 139 ms 54288 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 99 ms 54324 KB Output is correct
3 Correct 98 ms 54340 KB Output is correct
4 Correct 81 ms 54272 KB Output is correct
5 Correct 77 ms 54280 KB Output is correct
6 Correct 123 ms 54328 KB Output is correct
7 Correct 121 ms 54316 KB Output is correct
8 Correct 88 ms 54316 KB Output is correct
9 Correct 85 ms 54232 KB Output is correct
10 Correct 77 ms 54244 KB Output is correct
11 Correct 91 ms 54240 KB Output is correct
12 Correct 181 ms 54312 KB Output is correct
13 Correct 139 ms 54288 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 162 ms 104304 KB Output is correct
16 Correct 203 ms 129476 KB Output is correct
17 Correct 191 ms 154388 KB Output is correct
18 Correct 236 ms 154352 KB Output is correct
19 Correct 280 ms 154368 KB Output is correct
20 Correct 176 ms 104376 KB Output is correct
21 Correct 225 ms 129408 KB Output is correct
22 Correct 134 ms 79352 KB Output is correct
23 Correct 212 ms 130692 KB Output is correct
24 Correct 294 ms 105600 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2508 KB Output is correct
2 Correct 99 ms 54324 KB Output is correct
3 Correct 98 ms 54340 KB Output is correct
4 Correct 81 ms 54272 KB Output is correct
5 Correct 77 ms 54280 KB Output is correct
6 Correct 123 ms 54328 KB Output is correct
7 Correct 121 ms 54316 KB Output is correct
8 Correct 88 ms 54316 KB Output is correct
9 Correct 85 ms 54232 KB Output is correct
10 Correct 77 ms 54244 KB Output is correct
11 Correct 91 ms 54240 KB Output is correct
12 Correct 181 ms 54312 KB Output is correct
13 Correct 139 ms 54288 KB Output is correct
14 Correct 4 ms 5708 KB Output is correct
15 Correct 162 ms 104304 KB Output is correct
16 Correct 203 ms 129476 KB Output is correct
17 Correct 191 ms 154388 KB Output is correct
18 Correct 236 ms 154352 KB Output is correct
19 Correct 280 ms 154368 KB Output is correct
20 Correct 176 ms 104376 KB Output is correct
21 Correct 225 ms 129408 KB Output is correct
22 Correct 134 ms 79352 KB Output is correct
23 Correct 212 ms 130692 KB Output is correct
24 Correct 294 ms 105600 KB Output is correct
25 Runtime error 76 ms 4868 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -