Submission #437820

#	Time	Username	Problem	Language	Result	Execution time	Memory
437820		SuffixAutomata	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	445 ms	225316 KiB

dungeons

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

int lose[400005], win[500005];
int he[400005], loseget[400005];
int n;

bool sub2 = 1;
bool sub4 = 1;
struct s2tag {
  int en;
  ll enExp;
  ll gap;
} s2fw[12][11][400005];
// s2fw[i][j][k] = from k, beat all <4^i, go 4^j steps
// gap: least amount of health you need to begin with for s2fw[i][j][k] to not
// work

ll p5[30];

s2tag mer(s2tag a, s2tag b) {
  return {b.en, a.enExp + b.enExp, max(0ll, min(a.gap, b.gap - a.enExp))};
}

#define ex4(n) p5[n]

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w,
          std::vector<int> l) {
  p5[0] = 1;
  for (int i = 1; i <= 24; i++)
    p5[i] = p5[i - 1] * 5;
  ::n = n;
  for (int i = 0; i < n; i++) {
    lose[i] = l[i];
    win[i] = w[i];
    he[i] = s[i];
    loseget[i] = p[i];
    if (he[i] != loseget[i])
      sub2 = 0;
  }
  win[n] = n;
  for (int i = 0; i < 12; i++) {
    for (int k = 0; k <= n; k++) {
      if (he[k] < ex4(i))
        s2fw[i][0][k] = {win[k], he[k], 1ull << 60};
      else
        s2fw[i][0][k] = {lose[k], loseget[k], he[k]};
    }
    for (int j = 0; j < 10; j++)
      for (int k = 0; k <= n; k++) {
        s2fw[i][j + 1][k] = s2fw[i][j][k];
        for (int _ = 0; _ < 4; _++)
          s2fw[i][j + 1][k] =
              mer(s2fw[i][j + 1][k], s2fw[i][j][s2fw[i][j + 1][k].en]);
      }
  }
  return;
}

long long simulate(int x, int _z) {
  ll z = _z;
  while (x != n) {
    int r = 0;
    while (ex4(r + 1) < z)
      r++;
    r = min(r, 12);
    for (int j = 0; j >= 0; j--)
      for (int _ = 0; _ < 4; _++)
        if (mer(s2tag{x, z, 1ll << 60}, s2fw[r][j][x]).gap > 0) {
          z += s2fw[r][j][x].enExp;
          x = s2fw[r][j][x].en;
        }
    if (z >= he[x]) {
      z += he[x];
      x = win[x];
    } else {
      assert(0);
      z += loseget[x];
      x = lose[x];
    }
  }
  return z;
}

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