#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
const int MX = 50005;
const int LG = 25;
const int STA = 25;
int n,s[MX],p[MX],w[MX],l[MX];
pii win[MX][LG+5];
int wincond[MX][LG+1];
pii lose[STA+1][MX][LG+1];
int losecond[STA+1][MX][LG+1];
vi st;
void init(signed n0, vector<signed> s0, vector<signed> p0, vector<signed> w0, vector<signed> l0) {
n = n0;
REP(i,n){
s[i] = s0[i];
p[i] = p0[i];
w[i] = w0[i];
l[i] = l0[i];
}
st.pb(2);
FOR(i,1,STA) st.pb(2*st.back());
w[n] = n;
l[n] = n;
s[n] = 0;
p[n] = 0;
REP(i,n+1){
win[i][0] = {w[i],s[i]};
wincond[i][0] = s[w[i]]-s[i];
}
FOR(j,1,LG+1){
REP(i,n+1){
win[i][j] = {win[win[i][j-1].F][j-1].F,win[win[i][j-1].F][j-1].S+win[i][j-1].S};
wincond[i][j] = max(wincond[i][j-1],wincond[win[i][j-1].F][j-1]-win[i][j-1].S);
}
}
REP(stage,STA+1){
REP(i,n){
if(stage and s[i] <= st[stage-1]){
l[i] = w[i];
p[i] = s[i];
s[i] = (int)1e16;
}
}
REP(i,n+1){
lose[stage][i][0] = {l[i],p[i]};
losecond[stage][i][0] = s[l[i]]-p[i];
// int j = 0;
// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
}
FOR(j,1,LG+1){
REP(i,n+1){
lose[stage][i][j] = {lose[stage][lose[stage][i][j-1].F][j-1].F,lose[stage][lose[stage][i][j-1].F][j-1].S+lose[stage][i][j-1].S};
losecond[stage][i][j] = min(losecond[stage][i][j-1],losecond[stage][lose[stage][i][j-1].F][j-1]-lose[stage][i][j-1].S);
// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
}
}
REP(i,n){
s[i] = s0[i];
p[i] = p0[i];
w[i] = w0[i];
l[i] = l0[i];
}
}
}
int simulate(signed x, signed z) {
int ind = x;
int ans = z;
int stage = 0;
while(ind != n){
// cout << ind << " " << ans << "\n";
if(s[ind] > ans){
while(stage < STA and st[stage] <= ans) stage++;
for(int j = LG; j >= 0; j --){
if(losecond[stage][ind][j] > ans){
ans += lose[stage][ind][j].S;
ind = lose[stage][ind][j].F;
}
}
if(s[ind] > ans){
ans += p[ind];
ind = l[ind];
}
}
else{
for(int j = LG; j >= 0; j --){
if(wincond[ind][j] <= ans){
ans += win[ind][j].S;
ind = win[ind][j].F;
}
}
ans += s[ind];
ind = w[ind];
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
716 KB |
Output is correct |
2 |
Correct |
1 ms |
844 KB |
Output is correct |
3 |
Correct |
25 ms |
33872 KB |
Output is correct |
4 |
Correct |
1553 ms |
831028 KB |
Output is correct |
5 |
Correct |
24 ms |
33868 KB |
Output is correct |
6 |
Correct |
1319 ms |
830852 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
17356 KB |
Output is correct |
2 |
Runtime error |
204 ms |
15144 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
17356 KB |
Output is correct |
2 |
Correct |
1447 ms |
831644 KB |
Output is correct |
3 |
Correct |
1357 ms |
831656 KB |
Output is correct |
4 |
Correct |
1418 ms |
831628 KB |
Output is correct |
5 |
Correct |
1336 ms |
831628 KB |
Output is correct |
6 |
Correct |
1449 ms |
831556 KB |
Output is correct |
7 |
Correct |
1466 ms |
831680 KB |
Output is correct |
8 |
Correct |
1333 ms |
831648 KB |
Output is correct |
9 |
Correct |
1335 ms |
831632 KB |
Output is correct |
10 |
Correct |
1397 ms |
831568 KB |
Output is correct |
11 |
Correct |
1755 ms |
831684 KB |
Output is correct |
12 |
Correct |
2105 ms |
831696 KB |
Output is correct |
13 |
Correct |
1600 ms |
831676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
17356 KB |
Output is correct |
2 |
Correct |
1447 ms |
831644 KB |
Output is correct |
3 |
Correct |
1357 ms |
831656 KB |
Output is correct |
4 |
Correct |
1418 ms |
831628 KB |
Output is correct |
5 |
Correct |
1336 ms |
831628 KB |
Output is correct |
6 |
Correct |
1449 ms |
831556 KB |
Output is correct |
7 |
Correct |
1466 ms |
831680 KB |
Output is correct |
8 |
Correct |
1333 ms |
831648 KB |
Output is correct |
9 |
Correct |
1335 ms |
831632 KB |
Output is correct |
10 |
Correct |
1397 ms |
831568 KB |
Output is correct |
11 |
Correct |
1755 ms |
831684 KB |
Output is correct |
12 |
Correct |
2105 ms |
831696 KB |
Output is correct |
13 |
Correct |
1600 ms |
831676 KB |
Output is correct |
14 |
Correct |
13 ms |
17356 KB |
Output is correct |
15 |
Correct |
1347 ms |
831796 KB |
Output is correct |
16 |
Correct |
1450 ms |
831812 KB |
Output is correct |
17 |
Correct |
1488 ms |
831768 KB |
Output is correct |
18 |
Correct |
1493 ms |
831680 KB |
Output is correct |
19 |
Correct |
1470 ms |
831788 KB |
Output is correct |
20 |
Correct |
1484 ms |
831680 KB |
Output is correct |
21 |
Correct |
1365 ms |
831660 KB |
Output is correct |
22 |
Correct |
1600 ms |
831648 KB |
Output is correct |
23 |
Correct |
1651 ms |
831660 KB |
Output is correct |
24 |
Correct |
1990 ms |
831600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
17356 KB |
Output is correct |
2 |
Correct |
1447 ms |
831644 KB |
Output is correct |
3 |
Correct |
1357 ms |
831656 KB |
Output is correct |
4 |
Correct |
1418 ms |
831628 KB |
Output is correct |
5 |
Correct |
1336 ms |
831628 KB |
Output is correct |
6 |
Correct |
1449 ms |
831556 KB |
Output is correct |
7 |
Correct |
1466 ms |
831680 KB |
Output is correct |
8 |
Correct |
1333 ms |
831648 KB |
Output is correct |
9 |
Correct |
1335 ms |
831632 KB |
Output is correct |
10 |
Correct |
1397 ms |
831568 KB |
Output is correct |
11 |
Correct |
1755 ms |
831684 KB |
Output is correct |
12 |
Correct |
2105 ms |
831696 KB |
Output is correct |
13 |
Correct |
1600 ms |
831676 KB |
Output is correct |
14 |
Correct |
13 ms |
17356 KB |
Output is correct |
15 |
Correct |
1347 ms |
831796 KB |
Output is correct |
16 |
Correct |
1450 ms |
831812 KB |
Output is correct |
17 |
Correct |
1488 ms |
831768 KB |
Output is correct |
18 |
Correct |
1493 ms |
831680 KB |
Output is correct |
19 |
Correct |
1470 ms |
831788 KB |
Output is correct |
20 |
Correct |
1484 ms |
831680 KB |
Output is correct |
21 |
Correct |
1365 ms |
831660 KB |
Output is correct |
22 |
Correct |
1600 ms |
831648 KB |
Output is correct |
23 |
Correct |
1651 ms |
831660 KB |
Output is correct |
24 |
Correct |
1990 ms |
831600 KB |
Output is correct |
25 |
Correct |
1365 ms |
830788 KB |
Output is correct |
26 |
Correct |
1430 ms |
831800 KB |
Output is correct |
27 |
Correct |
1374 ms |
831568 KB |
Output is correct |
28 |
Correct |
1397 ms |
831612 KB |
Output is correct |
29 |
Correct |
1504 ms |
831612 KB |
Output is correct |
30 |
Correct |
1499 ms |
831760 KB |
Output is correct |
31 |
Correct |
1454 ms |
831860 KB |
Output is correct |
32 |
Correct |
1906 ms |
831740 KB |
Output is correct |
33 |
Correct |
1959 ms |
831588 KB |
Output is correct |
34 |
Correct |
2760 ms |
831420 KB |
Output is correct |
35 |
Correct |
1720 ms |
831652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
17356 KB |
Output is correct |
2 |
Runtime error |
204 ms |
15144 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |