제출 #1021078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021078		awu	던전 (IOI21_dungeons)	C++17	11 / 100	1223 ms	2097152 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;
}
 
int n;
vector<signed> s, p, w, l;
vector<vector<vector<signed>>> jmp, mx;
vector<vector<vector<int>>> prec; // mx is exc
 
int nk = 25;
int jl = 20;
 
void init(signed N, vector<signed> S, vector<signed> P, vector<signed> W, vector<signed> L) {
  pstart();
  n = N;
  s = S;
  p = P;
  w = W;
  l = L;
  jmp = mx = vector<vector<vector<signed>>>(nk, vector<vector<signed>>(n + 1, vector<signed>(jl)));
  prec = vector<vector<vector<int>>>(nk, vector<vector<int>>(n + 1, vector<int>(jl)));
  for(int i = 0; i < nk; i++) {
    for(int j = 0; j < n; j++) {
      if((1 << i) >= s[j]) {
        jmp[i][j][0] = w[j];
        prec[i][j][0] = s[j];
        mx[i][j][0] = 1 << 30;
      } else {
        jmp[i][j][0] = l[j];
        prec[i][j][0] = p[j];
        mx[i][j][0] = s[j];
      }
    }
    fill(all(jmp[i][n]), n);
    fill(all(mx[i][n]), 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] - prec[i][j][k - 1]));
      }
    }
  }
  pend();
  debug(pt);
  assert(pt < 2000);
}
 
int fastlog2(int x) {
  return 63 - __builtin_clzll(x);
}
 
int simulate(signed x, signed Z) {
  int z = Z;
  int li = -1;
  int icnt = 0;
  while(x != n) {
    icnt++;
    assert(icnt < 40);
    if(z >= s[x]) {
      z += s[x];
      x = w[x];
    } else {
      z += p[x];
      x = l[x];
    }
    int i = fastlog2(z);
    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;
}

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