제출 #993297

#제출 시각아이디문제언어결과실행 시간메모리
993297pavement던전 (IOI21_dungeons)C++17
0 / 100
10 ms13404 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back const int MAX_N = 400000, BAND_LIM = 24, DECOMP_LIM = 12; int n, to[BAND_LIM][DECOMP_LIM][MAX_N + 1], wei[BAND_LIM][DECOMP_LIM][MAX_N + 1], lim[BAND_LIM][DECOMP_LIM][MAX_N + 1], s[MAX_N + 1], p[MAX_N + 1], w[MAX_N + 1], l[MAX_N + 1]; ll winner[MAX_N + 1]; void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { ::n = n; copy(s.begin(), s.end(), ::s); copy(p.begin(), p.end(), ::p); copy(w.begin(), w.end(), ::w); copy(l.begin(), l.end(), ::l); ::w[n] = n; ::l[n] = n; for (int i = n - 1; i >= 0; i--) { winner[i] = winner[w[i]] + s[i]; } for (int b = 0; b < BAND_LIM; b++) { int lb = (1 << b), rb = (1 << (b + 1)) - 1; for (int i = 0; i <= n; i++) { if (s[i] < lb) { // instant-win to[b][0][i] = w[i]; wei[b][0][i] = s[i]; lim[b][0][i] = INT_MAX; } else if (s[i] > rb) { // instant-lose to[b][0][i] = l[i]; wei[b][0][i] = p[i]; lim[b][0][i] = INT_MAX; } else { to[b][0][i] = l[i]; wei[b][0][i] = p[i]; lim[b][0][i] = s[i]; } } for (int k = 1; k < DECOMP_LIM; k++) { for (int i = 0; i <= n; i++) { to[b][k][i] = to[b][k - 1][to[b][k - 1][to[b][k - 1][to[b][k - 1][i]]]]; wei[b][k][i] = min(rb, wei[b][k - 1][i] + wei[b][k - 1][to[b][k - 1][i]] + wei[b][k - 1][to[b][k - 1][to[b][k - 1][i]]] + wei[b][k - 1][to[b][k - 1][to[b][k - 1][to[b][k - 1][i]]]]); lim[b][k][i] = max(0, min({lim[b][k - 1][i], lim[b][k - 1][to[b][k - 1][i]] - wei[b][k - 1][i], lim[b][k - 1][to[b][k - 1][to[b][k - 1][to[b][k - 1][i]]]] - (wei[b][k - 1][i] + wei[b][k - 1][to[b][k - 1][i]]), lim[b][k - 1][to[b][k - 1][to[b][k - 1][to[b][k - 1][to[b][k - 1][i]]]]] - (wei[b][k - 1][i] + wei[b][k - 1][to[b][k - 1][i]] + wei[b][k - 1][to[b][k - 1][to[b][k - 1][i]]])})); } } } } ll simulate(int x, int _z) { ll z = _z; for (int b = 0; b < BAND_LIM; b++) { int rb = (1 << (b + 1)) - 1; if (z > rb) { // past this band continue; } for (int k = DECOMP_LIM - 1; k >= 0; k--) { for (int rep = 0; rep < 3; rep++) { if (lim[b][k][x] <= z || wei[b][k][x] > rb - z) { continue; } z += wei[b][k][x]; x = to[b][k][x]; } } if (x == n) { return z; } for (int iter = 0; iter < 2; iter++) { if (z >= s[x]) { z += s[x]; x = w[x]; } else { z += p[x]; x = l[x]; } if (x == n) { return z; } } assert(z > rb); } // win all the way return z + winner[x]; }
#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...