Submission #437840

#TimeUsernameProblemLanguageResultExecution timeMemory
437840SuffixAutomataDungeons Game (IOI21_dungeons)C++17
37 / 100
7110 ms865972 KiB
#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[10][9][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(1ll * 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] * 6; ::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 < 10; 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 < 8; j++) for (int k = 0; k <= n; k++) { s2fw[i][j + 1][k] = s2fw[i][j][k]; for (int _ = 0; _ < 5; _++) 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, 9); for (int j = 8; j >= 0; j--) for (int _ = 0; _ < 5; _++) if (mer(s2tag{x, z, 1ll << 29}, 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; }

Compilation message (stderr)

dungeons.cpp: In function 's2tag mer(s2tag, s2tag)':
dungeons.cpp:24: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)), (((ll)b.s2tag::gap) - a.s2tag::enExp))))' from 'long long int' to 'int' [-Wnarrowing]
   24 |   return {b.en, a.enExp + b.enExp, max(0ll, min(1ll * a.gap, b.gap - a.enExp))};
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...