This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int inf = 0x3f3f3f3f,N = 4e5 + 5,B = 16,L = 7;
//The key observation is that every time we win our damage doubles
struct info{
//next place and the attack you need to win a game
int nxt,atk;
//overall attack we gained
ll sum;
info operator + (const info a)const{
int res;
if(a.atk == inf)res = atk;
else res = max(0ll,min((ll)atk,a.atk - sum));
return (info){a.nxt,res,sum + a.sum};
}
}f[L][25][N];
int n,powB[L];
vi s,p,w,l;
ll simulate(int x,int z){
int i = 0;
while(114514){
if(i + 1 < L && z > powB[i+1]) ++i;
for(int j = 24;j >= 0;j--){
info now = f[i][j][x];
if(now.nxt == n)continue;//jumping too far
if(now.atk != inf)continue;//
if(now.atk <= z)continue;//already winning
z += now.sum, x = now.nxt;
}
if(z >= s[x]) z += s[x], x = w[x];
else z += p[x], x = l[x];
if(x == n)return z;
}
}
void prework(int X,int k){
for(int i = 0;i < n;i++){
if(X >= s[i]){
f[k][0][i] = (info){w[i],inf,s[i]};
}else f[k][0][i] = (info){l[i],s[i],p[i]};
}
for(int j = 1;j < 25;j++)for(int i = 0;i < n;i++){
info t = f[k][j-1][i];
f[k][j][i] = t + f[k][j-1][t.nxt];
}
}
void init(int _n,vi _s,vi _p,vi _w,vi _l){
n = _n,s = _s,p = _p,w = _w,l = _l;
w.pb(n),l.pb(n);
powB[0] = 1;
for(int d = 0;d < L;d++){
prework(powB[d],d);
powB[d+1] = powB[d] * B;
}
}
Compilation message (stderr)
dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:56:19: warning: iteration 6 invokes undefined behavior [-Waggressive-loop-optimizations]
56 | powB[d+1] = powB[d] * B;
| ~~~~~~~~~~^~~~~~~~~~~~~
dungeons.cpp:54:21: note: within this loop
54 | for(int d = 0;d < L;d++){
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |