Submission #1021760

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021760		awu	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2915 ms	902792 KiB

dungeons

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
// const ll inf = 1ll << 60;
const int inf = 1 << 30;

template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  out << "(" << p.f << ", " << p.s << ")";
  return out;
}
template<typename T>
typename enable_if<!is_same<T, const char *>::value && !is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T o) {
  out << "{";
  int g = o.size();
  for(auto i : o) out << i << (--g ? ", " : "");
  out << "}";
  return out;
}
// void my_assert(bool b) {
//   if(!b) {
//     cerr << "Assertion failed" << endl;
//     *((volatile int*)0);
//   }
// }
// #undef assert
// #define assert my_assert

int millis() {
  return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
}
int pt = 0;
int start_time;
void pstart() {
  start_time = millis();
}
void pend() {
  pt += millis() - start_time;
}

const int nk = 7;
const int jl = 20;

int n;
vector<signed> s, p, w, l;
signed jmp[nk][400005][jl], mx[nk][400005][jl];
int prec[nk][400005][jl]; // mx is exc

void init(signed N, vector<signed> S, vector<signed> P, vector<signed> W, vector<signed> L) {
  pstart();
  n = move(N);
  s = move(S);
  p = move(P);
  w = move(W);
  l = move(L);
  for(int i = 0; i < nk; i++) {
    for(int j = 0; j < n; j++) {
      if((1 << (i * 4)) >= s[j]) {
        jmp[i][j][0] = w[j];
        prec[i][j][0] = s[j];
        mx[i][j][0] = inf;
      } else {
        jmp[i][j][0] = l[j];
        prec[i][j][0] = p[j];
        mx[i][j][0] = s[j];
      }
    }
    for(int j = 0; j < jl; j++) {
      jmp[i][n][j] = n;
      mx[i][n][j] = inf;
    }
    for(int k = 1; k < jl; k++) {
      for(int j = 0; j < n; j++) {
        jmp[i][j][k] = jmp[i][jmp[i][j][k - 1]][k - 1];
        prec[i][j][k] = prec[i][j][k - 1] + prec[i][jmp[i][j][k - 1]][k - 1];
        mx[i][j][k] = min(mx[i][j][k - 1], (signed)max(0ll, mx[i][jmp[i][j][k - 1]][k - 1] == inf ? inf : mx[i][jmp[i][j][k - 1]][k - 1] - prec[i][j][k - 1]));
      }
    }
  }
  pend();
  // assert(pt < 2000);
}

int fastlog2(int x) {
  return 63 - __builtin_clzll(x);
}

int simulate(signed x, signed Z) {
  int z = Z;
  int li = -1;
  while(x != n) {
    if(z >= s[x]) {
      z += s[x];
      x = w[x];
    } else {
      z += p[x];
      x = l[x];
    }
    int i = fastlog2(z) / 4;
    // assert(z >= 1e7 || i > li);
    li = i;
    i = min(i, nk - 1);
    for(int k = jl - 1; k >= 0; k--) {
      if(z < mx[i][x][k]) {
        z += prec[i][x][k];
        x = jmp[i][x][k];
        if(x == n) break;
      }
    }
    // assert(x == n || z >= s[x]);
  }
  return z;
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:99:7: warning: variable 'li' set but not used [-Wunused-but-set-variable]
   99 |   int li = -1;
      |       ^~

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