#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=50010;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll nxt[25][25][Nmax], sum[25][25][Nmax], mx[25][25][Nmax];
void init(int n, std::vector<int> S_, std::vector<int> P_, std::vector<int> W_, std::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];
for(int i=0; i<25; i++) {
for(int j=0; j<N; j++) {
if(S[j]>=(1<<(i+1))) nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=(1<<(i+1))-1-P[j];
else if(S[j]<=(1<<i)) nxt[i][0][j]=W[j], sum[i][0][j]=S[j], mx[i][0][j]=(1<<(i+1))-1-S[j];
else nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=min(S[j]-1, (1<<(i+1))-1-P[j]);
}
nxt[i][0][N]=N, sum[i][0][N]=0, mx[i][0][N]=(1<<(i+1))-1;
for(int j=1; j<25; j++) for(int k=0; k<=N; k++) {
nxt[i][j][k]=nxt[i][j-1][nxt[i][j-1][k]];
sum[i][j][k]=sum[i][j-1][k]+sum[i][j-1][nxt[i][j-1][k]];
mx[i][j][k]=min(mx[i][j-1][k], mx[i][j-1][nxt[i][j-1][k]]-sum[i][j-1][k]);
}
}
for(int j=0; j<25; j++) for(int k=0; k<=N; k++) mx[24][j][k]=LLONG_MAX;
}
long long simulate(int x, int z) {
int k=x; ll v=z;
for(int i=0; i<25; i++) {
int kk=k; ll vv=v;
for(int j=24; j>=0; j--) if(vv<=mx[i][j][kk]) vv+=sum[i][j][kk], kk=nxt[i][j][kk];
if(kk==N) {
for(int j=24; j>=0; j--) if(nxt[i][j][k]!=N) v+=sum[i][j][k], k=nxt[i][j][k];
if(k!=N) v+=sum[i][0][k], k=nxt[i][0][k];
return v;
}
if(vv<(1<<(i+1))) {
if(vv>=S[kk]) vv+=S[kk], kk=W[kk];
else vv+=P[kk], kk=L[kk];
}
k=kk, v=vv;
}
}
Compilation message
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
45 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
398512 KB |
Output is correct |
2 |
Correct |
53 ms |
402516 KB |
Output is correct |
3 |
Correct |
59 ms |
416080 KB |
Output is correct |
4 |
Correct |
272 ms |
736552 KB |
Output is correct |
5 |
Correct |
62 ms |
421968 KB |
Output is correct |
6 |
Correct |
258 ms |
737660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
413248 KB |
Output is correct |
2 |
Runtime error |
131 ms |
17964 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
413264 KB |
Output is correct |
2 |
Correct |
839 ms |
738820 KB |
Output is correct |
3 |
Correct |
838 ms |
739280 KB |
Output is correct |
4 |
Correct |
776 ms |
738652 KB |
Output is correct |
5 |
Correct |
775 ms |
738608 KB |
Output is correct |
6 |
Correct |
1029 ms |
738648 KB |
Output is correct |
7 |
Correct |
1136 ms |
738764 KB |
Output is correct |
8 |
Correct |
1160 ms |
738504 KB |
Output is correct |
9 |
Correct |
566 ms |
738516 KB |
Output is correct |
10 |
Correct |
1055 ms |
738428 KB |
Output is correct |
11 |
Correct |
1321 ms |
738428 KB |
Output is correct |
12 |
Correct |
2876 ms |
739032 KB |
Output is correct |
13 |
Correct |
3011 ms |
739008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
413264 KB |
Output is correct |
2 |
Correct |
839 ms |
738820 KB |
Output is correct |
3 |
Correct |
838 ms |
739280 KB |
Output is correct |
4 |
Correct |
776 ms |
738652 KB |
Output is correct |
5 |
Correct |
775 ms |
738608 KB |
Output is correct |
6 |
Correct |
1029 ms |
738648 KB |
Output is correct |
7 |
Correct |
1136 ms |
738764 KB |
Output is correct |
8 |
Correct |
1160 ms |
738504 KB |
Output is correct |
9 |
Correct |
566 ms |
738516 KB |
Output is correct |
10 |
Correct |
1055 ms |
738428 KB |
Output is correct |
11 |
Correct |
1321 ms |
738428 KB |
Output is correct |
12 |
Correct |
2876 ms |
739032 KB |
Output is correct |
13 |
Correct |
3011 ms |
739008 KB |
Output is correct |
14 |
Correct |
62 ms |
421204 KB |
Output is correct |
15 |
Correct |
781 ms |
738876 KB |
Output is correct |
16 |
Correct |
840 ms |
739200 KB |
Output is correct |
17 |
Correct |
1006 ms |
738560 KB |
Output is correct |
18 |
Correct |
959 ms |
738640 KB |
Output is correct |
19 |
Correct |
965 ms |
738732 KB |
Output is correct |
20 |
Correct |
979 ms |
738476 KB |
Output is correct |
21 |
Correct |
1135 ms |
738580 KB |
Output is correct |
22 |
Correct |
1146 ms |
738640 KB |
Output is correct |
23 |
Correct |
1478 ms |
738892 KB |
Output is correct |
24 |
Correct |
1836 ms |
738700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
413264 KB |
Output is correct |
2 |
Correct |
839 ms |
738820 KB |
Output is correct |
3 |
Correct |
838 ms |
739280 KB |
Output is correct |
4 |
Correct |
776 ms |
738652 KB |
Output is correct |
5 |
Correct |
775 ms |
738608 KB |
Output is correct |
6 |
Correct |
1029 ms |
738648 KB |
Output is correct |
7 |
Correct |
1136 ms |
738764 KB |
Output is correct |
8 |
Correct |
1160 ms |
738504 KB |
Output is correct |
9 |
Correct |
566 ms |
738516 KB |
Output is correct |
10 |
Correct |
1055 ms |
738428 KB |
Output is correct |
11 |
Correct |
1321 ms |
738428 KB |
Output is correct |
12 |
Correct |
2876 ms |
739032 KB |
Output is correct |
13 |
Correct |
3011 ms |
739008 KB |
Output is correct |
14 |
Correct |
62 ms |
421204 KB |
Output is correct |
15 |
Correct |
781 ms |
738876 KB |
Output is correct |
16 |
Correct |
840 ms |
739200 KB |
Output is correct |
17 |
Correct |
1006 ms |
738560 KB |
Output is correct |
18 |
Correct |
959 ms |
738640 KB |
Output is correct |
19 |
Correct |
965 ms |
738732 KB |
Output is correct |
20 |
Correct |
979 ms |
738476 KB |
Output is correct |
21 |
Correct |
1135 ms |
738580 KB |
Output is correct |
22 |
Correct |
1146 ms |
738640 KB |
Output is correct |
23 |
Correct |
1478 ms |
738892 KB |
Output is correct |
24 |
Correct |
1836 ms |
738700 KB |
Output is correct |
25 |
Correct |
275 ms |
738060 KB |
Output is correct |
26 |
Correct |
826 ms |
739160 KB |
Output is correct |
27 |
Correct |
782 ms |
738528 KB |
Output is correct |
28 |
Correct |
794 ms |
738552 KB |
Output is correct |
29 |
Correct |
896 ms |
739092 KB |
Output is correct |
30 |
Correct |
1102 ms |
738852 KB |
Output is correct |
31 |
Correct |
1257 ms |
738388 KB |
Output is correct |
32 |
Correct |
1421 ms |
738644 KB |
Output is correct |
33 |
Correct |
999 ms |
738956 KB |
Output is correct |
34 |
Correct |
1866 ms |
738708 KB |
Output is correct |
35 |
Correct |
1052 ms |
738660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
59 ms |
413248 KB |
Output is correct |
2 |
Runtime error |
131 ms |
17964 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |