제출 #437842

#제출 시각아이디문제언어결과실행 시간메모리
437842SuffixAutomata던전 (IOI21_dungeons)C++17
89 / 100
7108 ms865404 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) { 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 <= 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; }

컴파일 시 표준 에러 (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))};
      |                                    ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#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...