제출 #439239

#제출 시각아이디문제언어결과실행 시간메모리
439239Sorting던전 (IOI21_dungeons)C++17
37 / 100
7059 ms198840 KiB
#include "dungeons.h" #include <vector> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 4e5 + 3; const int C = 10000; const int LOGN = 19; const ll INF = 1e18; int n; vector<int> s, p, w, l; array<ll, 3> up[LOGN][N]; // pos, strength, max array<ll, 2> only_win[N]; void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) { n = _n, swap(s, _s), swap(p, _p), swap(w, _w), swap(l, _l); for(int i = 0; i < n; ++i){ if(s[i] <= C) up[0][i] = {i, 0, -INF}; else up[0][i] = {i, 0, -s[i]}; } for(int j = 1; j < LOGN; ++j){ for(int i = 0; i < n; ++i){ if(up[j - 1][i][0] == n){ up[j][i] = {n, -1, -1}; continue; } int a = up[j - 1][i][0], b; ll add; if(s[a] <= C){ b = w[a]; add = s[a]; } else{ b = l[a]; add = p[a]; } if(b == n || up[j - 1][b][0] == n){ up[j][i] = {n, -1, -1}; continue; } up[j][i][0] = up[j - 1][b][0]; up[j][i][1] = up[j - 1][i][1] + add + up[j - 1][b][1]; up[j][i][2] = max(up[j - 1][i][2], up[j - 1][i][1] + add + up[j - 1][b][2]); } } only_win[n] = {0, 0}; for(int i = n - 1; i >= 0; --i){ only_win[i][0] = max((ll)s[i], only_win[w[i]][0] - s[i]); only_win[i][1] = s[i] + only_win[w[i]][1]; } } long long simulate(int x, int z) { ll ans = z; while(ans < C && x != n){ if(ans >= s[x]){ ans += s[x]; x = w[x]; } else{ ans += p[x]; x = l[x]; } } int cnt = 0; while(x != n){ if(ans >= only_win[x][0]){ ans += only_win[x][1]; return ans; } for(int j = LOGN - 1; j >= 0; --j){ if(up[j][x][0] == n) continue; if(up[j][x][2] + ans < 0){ ans += up[j][x][1]; x = up[j][x][0]; if(s[x] <= ans){ ans += s[x]; x = w[x]; } else{ ans += p[x]; x = l[x]; } if(x == n) return ans; } } assert(s[x] > C); if(s[x] <= ans){ ans += s[x]; x = w[x]; } ++cnt; //assert(cnt <= 1003); } return ans; }
#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...