Submission #446590

#	Time	Username	Problem	Language	Result	Execution time	Memory
446590		SuffixAutomata	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	4086 ms	1046196 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;
  int gap;
} s2fw[9][12][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) {
  ll h = b.gap - a.enExp;
  if (b.gap == 1ll << 29)
    h = 1 << 29;
  return {b.en, a.enExp + b.enExp, max(0ll, min(1ll * a.gap, h))};
}

#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 <= 19; i++)
    p5[i] = p5[i - 1] * 9;
  ::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 < 9; i++) {
    for (int k = 0; k <= n; k++) {
      if (he[k] < ex4(i))
        s2fw[i][0][k] = {win[k], he[k], 1ll << 29};
      else
        s2fw[i][0][k] = {lose[k], loseget[k], he[k]};
    }
    for (int j = 0; j < 11; j++)
      for (int k = 0; k <= n; k++) {
        s2fw[i][j + 1][k] = s2fw[i][j][k];
        for (int _ = 0; _ < 3; _++)
          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, 8);
    for (int j = 11; j >= 0; j--)
      for (int _ = 0; _ < 3; _++)
        if (s2fw[r][j][x].gap > z) {
          z += s2fw[r][j][x].enExp;
          x = s2fw[r][j][x].en;
        } else
          break;
    if (z >= he[x]) {
      z += he[x];
      x = win[x];
    }
  }
  return z;
}

Compilation message (stderr)

dungeons.cpp: In function 's2tag mer(s2tag, s2tag)':
dungeons.cpp:27:39: warning: narrowing conversion of '(long long int)std::max<long long int>(0, (* & std::min<long long int>((1 * ((long long int)a.s2tag::gap)), h)))' from 'long long int' to 'int' [-Wnarrowing]
   27 |   return {b.en, a.enExp + b.enExp, max(0ll, min(1ll * a.gap, h))};
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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