Submission #442901

#TimeUsernameProblemLanguageResultExecution timeMemory
442901JvThunderDungeons Game (IOI21_dungeons)C++17
11 / 100
932 ms616232 KiB
#include "dungeons.h" #include <bits/stdc++.h> #define fir first #define sec second typedef long long ll; using namespace std; int N; vector<int> S,P,W,L; ll jump[11][22][50005]; // 8^b,2^jump,pos ll add[11][22][50005]; ll need[11][22][50005]; //beat all void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) { S = s; P = p; W = w; L = l; N = n; int tmp = 1; for(int bit=0;bit<=10;bit++) { int lim = tmp; for(int i=0;i<n;i++) { if(s[i]<=lim) add[bit][0][i] = s[i], jump[bit][0][i] = w[i], need[bit][0][i] = s[i]; else if(s[i]>8*lim) add[bit][0][i] = p[i], jump[bit][0][i] = l[i], need[bit][0][i] = 0; else add[bit][0][i] = 0, jump[bit][0][i] = i, need[bit][0][i] = 0; } need[bit][0][n] = 0, add[bit][0][n] = 0, jump[bit][0][n] = n; for(int i=1;i<=21;i++) { for(int j=0;j<=n;j++) { int nxt = jump[bit][i-1][j]; add[bit][i][j] = add[bit][i-1][j] + add[bit][i-1][nxt]; need[bit][i][j] = max(need[bit][i-1][j], need[bit][i-1][nxt]); jump[bit][i][j] = jump[bit][i-1][nxt]; } } tmp *= 8; } return; } ll simulate(int x, int z) { ll pos = x; ll str = z; ll tmp = 1; ll phase = 0; while(pos!=N && phase<=10) { tmp *= 8; for(int i=21;i>=0;i--) { if(need[phase][i][pos]<=str && str+add[phase][i][pos]<=tmp && jump[phase][i][pos]!=N) { str += add[phase][i][pos]; pos = jump[phase][i][pos]; } } while(pos!=N && str<=tmp) { if(str>=S[pos]) str += S[pos], pos = W[pos]; else str += P[pos], pos = L[pos]; } phase++; } return str; }
#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...