#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 = 400005;
const int LG = 25;
const int STA = 5;
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(4);
FOR(i,1,STA) st.pb(4*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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
9 ms |
9164 KB |
Output is correct |
4 |
Correct |
403 ms |
220312 KB |
Output is correct |
5 |
Correct |
8 ms |
9164 KB |
Output is correct |
6 |
Correct |
415 ms |
221232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4812 KB |
Output is correct |
2 |
Runtime error |
2222 ms |
1048580 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4812 KB |
Output is correct |
2 |
Correct |
450 ms |
221196 KB |
Output is correct |
3 |
Correct |
426 ms |
221136 KB |
Output is correct |
4 |
Correct |
439 ms |
221280 KB |
Output is correct |
5 |
Correct |
442 ms |
221268 KB |
Output is correct |
6 |
Correct |
513 ms |
221168 KB |
Output is correct |
7 |
Correct |
534 ms |
221196 KB |
Output is correct |
8 |
Correct |
516 ms |
221160 KB |
Output is correct |
9 |
Correct |
477 ms |
221224 KB |
Output is correct |
10 |
Correct |
436 ms |
221128 KB |
Output is correct |
11 |
Correct |
607 ms |
221252 KB |
Output is correct |
12 |
Correct |
709 ms |
221252 KB |
Output is correct |
13 |
Correct |
631 ms |
221252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4812 KB |
Output is correct |
2 |
Correct |
450 ms |
221196 KB |
Output is correct |
3 |
Correct |
426 ms |
221136 KB |
Output is correct |
4 |
Correct |
439 ms |
221280 KB |
Output is correct |
5 |
Correct |
442 ms |
221268 KB |
Output is correct |
6 |
Correct |
513 ms |
221168 KB |
Output is correct |
7 |
Correct |
534 ms |
221196 KB |
Output is correct |
8 |
Correct |
516 ms |
221160 KB |
Output is correct |
9 |
Correct |
477 ms |
221224 KB |
Output is correct |
10 |
Correct |
436 ms |
221128 KB |
Output is correct |
11 |
Correct |
607 ms |
221252 KB |
Output is correct |
12 |
Correct |
709 ms |
221252 KB |
Output is correct |
13 |
Correct |
631 ms |
221252 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
460 ms |
221136 KB |
Output is correct |
16 |
Correct |
454 ms |
221124 KB |
Output is correct |
17 |
Correct |
481 ms |
221124 KB |
Output is correct |
18 |
Correct |
440 ms |
221252 KB |
Output is correct |
19 |
Correct |
483 ms |
221252 KB |
Output is correct |
20 |
Correct |
472 ms |
221252 KB |
Output is correct |
21 |
Correct |
483 ms |
221132 KB |
Output is correct |
22 |
Correct |
530 ms |
221252 KB |
Output is correct |
23 |
Correct |
558 ms |
221208 KB |
Output is correct |
24 |
Correct |
711 ms |
221136 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4812 KB |
Output is correct |
2 |
Correct |
450 ms |
221196 KB |
Output is correct |
3 |
Correct |
426 ms |
221136 KB |
Output is correct |
4 |
Correct |
439 ms |
221280 KB |
Output is correct |
5 |
Correct |
442 ms |
221268 KB |
Output is correct |
6 |
Correct |
513 ms |
221168 KB |
Output is correct |
7 |
Correct |
534 ms |
221196 KB |
Output is correct |
8 |
Correct |
516 ms |
221160 KB |
Output is correct |
9 |
Correct |
477 ms |
221224 KB |
Output is correct |
10 |
Correct |
436 ms |
221128 KB |
Output is correct |
11 |
Correct |
607 ms |
221252 KB |
Output is correct |
12 |
Correct |
709 ms |
221252 KB |
Output is correct |
13 |
Correct |
631 ms |
221252 KB |
Output is correct |
14 |
Correct |
6 ms |
4992 KB |
Output is correct |
15 |
Correct |
460 ms |
221136 KB |
Output is correct |
16 |
Correct |
454 ms |
221124 KB |
Output is correct |
17 |
Correct |
481 ms |
221124 KB |
Output is correct |
18 |
Correct |
440 ms |
221252 KB |
Output is correct |
19 |
Correct |
483 ms |
221252 KB |
Output is correct |
20 |
Correct |
472 ms |
221252 KB |
Output is correct |
21 |
Correct |
483 ms |
221132 KB |
Output is correct |
22 |
Correct |
530 ms |
221252 KB |
Output is correct |
23 |
Correct |
558 ms |
221208 KB |
Output is correct |
24 |
Correct |
711 ms |
221136 KB |
Output is correct |
25 |
Correct |
391 ms |
220368 KB |
Output is correct |
26 |
Correct |
435 ms |
221124 KB |
Output is correct |
27 |
Correct |
482 ms |
221380 KB |
Output is correct |
28 |
Correct |
455 ms |
221192 KB |
Output is correct |
29 |
Correct |
457 ms |
221268 KB |
Output is correct |
30 |
Correct |
493 ms |
221280 KB |
Output is correct |
31 |
Correct |
487 ms |
221192 KB |
Output is correct |
32 |
Correct |
713 ms |
221204 KB |
Output is correct |
33 |
Correct |
1343 ms |
221064 KB |
Output is correct |
34 |
Correct |
1584 ms |
221008 KB |
Output is correct |
35 |
Correct |
2726 ms |
221124 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
4812 KB |
Output is correct |
2 |
Runtime error |
2222 ms |
1048580 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |