Submission #832681

#TimeUsernameProblemLanguageResultExecution timeMemory
832681welleythDungeons Game (IOI21_dungeons)C++17
24 / 100
7047 ms830996 KiB
#include "dungeons.h" #include <bits/stdc++.h> using namespace std; constexpr int N = (int)5e4+1; constexpr int K = 26; #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") int s[N],p[N],w[N],l[N]; int n; long long go[K][K][N]; long long sum[K][K][N]; long long goWin[N]; bool win[K][K][N]; long long maxPref[K][K][N]; vector<int> SValues; void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) { n = _n; for(int i = 0; i < n; i++){ s[i] = _s[i]; p[i] = _p[i]; w[i] = _w[i]; l[i] = _l[i]; SValues.push_back(s[i]); } SValues.push_back(0); sort(SValues.begin(),SValues.end()); SValues.erase(unique(SValues.begin(),SValues.end()),SValues.end()); int id = 0; for(int _t = 0; _t < K; _t++){ int val = (1 << _t); id = _t; for(int i = 0; i < n; i++){ int to = (val < s[i] ? l[i] : w[i]); int add = (val < s[i] ? p[i] : s[i]); go[id][0][i] = to; sum[id][0][i] = add; win[id][0][i] = (to == n); maxPref[id][0][i] = (s[i] < val ? 0 : -s[i]); // if(l[i] == n) sumLose[0][i] = (int)1e9; } for(int j = 1; j < K; j++){ for(int i = 0; i < n; i++){ go[id][j][i] = go[id][j-1][go[id][j-1][i]]; sum[id][j][i] = sum[id][j-1][i] + sum[id][j-1][go[id][j-1][i]]; win[id][j][i] = win[id][j-1][i] || win[id][j-1][go[id][j-1][i]]; maxPref[id][j][i] = max(maxPref[id][j-1][i], sum[id][j-1][i] + maxPref[id][j-1][go[id][j-1][i]]); } } id++; } for(int i = n-1; i >= 0; i--){ goWin[i] = goWin[w[i]] + s[i]; } return; } long long simulate(int _x, int _z) { int pos = _x; long long power = _z; while(power < SValues.back()){ int id = 0; for(int i = 0; i < K; i++) if(power >> i & 1) id = i; long long goal = (1 << (id + 1)); for(int i = K-1; i >= 0; i--){ if(!win[id][i][pos] && power + maxPref[id][i][pos] < 0){ power += sum[id][i][pos]; pos = go[id][i][pos]; } } if(pos == n) return power; int to = (power < s[pos] ? l[pos] : w[pos]); int add = (power < s[pos] ? p[pos] : s[pos]); power += add; pos = to; if(pos == n) return power; } return power + goWin[pos]; }

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:68:19: warning: unused variable 'goal' [-Wunused-variable]
   68 |         long long goal = (1 << (id + 1));
      |                   ^~~~
#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...