Submission #1023041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023041		NeroZein	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	163 ms	176588 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int D = 7;
const int LOG = 25;
const int N = 4e5 + 5; 

int n;
int nxt[D][LOG][N];
long long d[D][LOG][N];
vector<int> s, p, w, l;
vector<long long> strengths;

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_; 
  strengths.push_back(0); 
  for (int i = 0; i < n; ++i) {
    strengths.push_back(s[i]);
  }
  sort(strengths.begin(), strengths.end());
  strengths.resize(unique(strengths.begin(), strengths.end()) - strengths.begin());
  strengths.push_back(LLONG_MAX);
  for (int itr = 0; itr < (int) strengths.size(); ++itr) {
    int cur_strength = strengths[itr];
    d[itr][0][n] = 0;
    nxt[itr][0][n] = n; 
    for (int i = 0; i < n; ++i) {
      if (cur_strength >= s[i]) {
        d[itr][0][i] = s[i];
        nxt[itr][0][i] = w[i];
      } else {
        d[itr][0][i] = p[i];
        nxt[itr][0][i] = l[i];
      }
    }
    for (int j = 1; j < LOG; ++j) {
      for (int i = 0; i <= n; ++i) {
        d[itr][j][i] = d[itr][j - 1][i] + d[itr][j - 1][nxt[itr][j - 1][i]];
        nxt[itr][j][i] = nxt[itr][j - 1][nxt[itr][j - 1][i]];
      }
    }
  }
  return;
}

long long simulate(int x, int z) {
  long long strength = z; 
  while (x != n) {
    int itr = 0;
    for (int j = (int) strengths.size() - 1; j >= 0; --j) {
      if (strength >= strengths[j]) {
        itr = j;
        break; 
      }
    }
    for (int j = LOG - 1; j >= 0; --j) {
      if (strength + d[itr][j][x] < strengths[itr + 1]) {
        strength += d[itr][j][x];
        x = nxt[itr][j][x];
      }
    }
    if (x == n) { 
      return strength;
    }
    if (strength >= s[x]) {
      strength += s[x];
      x = w[x];
    } else {
      strength += p[x];
      x = l[x]; 
    }
  }
  return strength;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11