제출 #1079749

#제출 시각아이디문제언어결과실행 시간메모리
1079749GusterGoose27던전 (IOI21_dungeons)C++17
63 / 100
1739 ms1287972 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 5e4+5;//4e5+5; const ll MAXS = 1e18;; const int MAXB = 25; // will always terminate after 2^24 steps vector<int> s, p, w, l; int n; struct step { ll st, m; int f; // strength_gain, final, min to beat step() {} step(int i, int b) { // bucket id if (i == n) { st = 0; f = n; m = MAXS; } else { int lcut = (1<<b); if (lcut >= s[i]) { st = s[i]; f = w[i]; m = MAXS; } else { st = p[i]; f = l[i]; m = s[i]; } } } step(step &a, step &b) { st = min(MAXS, a.st+b.st); f = b.f; m = min(a.m, b.m-a.st); } }; step lift[MAXB][MAXB][MAXN]; // cutoff, lift num, start void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) { n = N; s = S; p = P; w = W; l = L; for (int c = 0; c < MAXB; c++) { for (int i = 0; i <= n; i++) lift[c][0][i] = step(i, c); for (int b = 1; b < MAXB; b++) { for (int i = 0; i <= n; i++) lift[c][b][i] = step(lift[c][b-1][i], lift[c][b-1][lift[c][b-1][i].f]); } } } ll simulate2(int x, ll z) { if (x == n) return z; int c = (z >= (1ll<<(MAXB-1)) ? MAXB-1 : 31-__builtin_clz(z)); // cerr << c << ' ' << z << '\n'; if (c == MAXB-1) return lift[c][MAXB-1][x].st + z; for (int b = MAXB-1; b >= 0; b--) { if (z < lift[c][b][x].m) return simulate2(lift[c][b][x].f, lift[c][b][x].st+z); } if (z < s[x]) return -1; // assert(z >= s[x]); return simulate2(w[x], z + s[x]); } ll simulate(int x, int z) { return simulate2(x, z); }
#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...