Submission #1210290

#TimeUsernameProblemLanguageResultExecution timeMemory
1210290steveonalexDungeons Game (IOI21_dungeons)C++20
63 / 100
3533 ms681352 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1ULL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll gcd(ll a, ll b){return __gcd(a, b);} ll lcm(ll a, ll b){return a / gcd(a, b) * b;} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ull mask){return __builtin_popcountll(mask);} int ctz(ull mask){return __builtin_ctzll(mask);} int logOf(ull mask){return 63 - __builtin_clzll(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} double rngesus_d(double l, double r){ double wow = (double) ((ull) rng()) / ((ull)(0-1)); return wow * (r - l) + l; } template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){ for(auto item: container) out << item << separator; out << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } #include "dungeons.h" const int N = 5e4 + 69; const int LOG_A = 24; const ll INF = 1e18 + 69; int n; int s[N], p[N], w[N], l[N]; ll nxt[LOG_A][N][LOG_A]; ll cost[LOG_A][N][LOG_A], barber[LOG_A][N][LOG_A]; int get_layer(ll z){ if (z == 0) return 0; return min(logOf(z), LOG_A - 1); } void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l){ n = _n; if (n >= N) assert(false); for(int i= 0; i < n; ++i) { s[i] = _s[i]; p[i] = _p[i]; w[i] = _w[i]; l[i] = _l[i]; } w[n] = l[n] = n; s[n] = p[n] = 0; for(int layer = 0; layer < LOG_A; ++layer){ vector<ll> s1(n+1), p1(n+1), w1(n+1); for(int i = 0; i <= n; ++i){ int cur = get_layer(s[i]); if (cur < layer){ s1[i] = INF; p1[i] = s[i]; w1[i] = w[i]; } else if (cur > layer){ s1[i] = INF; p1[i] = p[i]; w1[i] = l[i]; } else{ s1[i] = s[i]; p1[i] = p[i]; w1[i] = l[i]; } nxt[layer][i][0] = w1[i]; cost[layer][i][0] = p1[i]; barber[layer][i][0] = s1[i]; } for(int j = 1; j < LOG_A; ++j) { for(int i = 0; i <= n; ++i){ int prev = nxt[layer][i][j-1]; nxt[layer][i][j] = nxt[layer][prev][j-1]; cost[layer][i][j] = cost[layer][i][j-1] + cost[layer][prev][j-1]; barber[layer][i][j] = min(barber[layer][i][j-1], barber[layer][prev][j-1] - cost[layer][i][j-1]); } } } } ll simulate(int x, int z){ ll ans = z; while(true){ if (x == n) break; int layer = get_layer(ans); for(int j = LOG_A - 1; j >= 0; --j) { if (nxt[layer][x][j] == n) continue; if (get_layer(ans + cost[layer][x][j]) != layer) continue; if (ans >= barber[layer][x][j]) continue; ans += cost[layer][x][j]; x = nxt[layer][x][j]; } if (ans >= s[x]){ ans += s[x]; x = w[x]; } else{ ans += p[x]; x = l[x]; } } return ans; } /* 3 2 2 6 9 3 1 2 2 2 3 1 0 1 0 1 2 3 */
#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...