#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int Nmax=400010;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
vector<int> nxt[25][Nmax], mx[25][Nmax];
vector<ll> sum[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++) nxt[i][j].resize(i+1), mx[i][j].resize(i+1), sum[i][j].resize(i+1);
for(int i=0; i<25; i++) {
for(int j=0; j<N; j++) {
if(S[j]>=(1<<(i+1))) nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=(1<<(i+1))-1-P[j];
else if(S[j]<=(1<<i)) nxt[i][j][0]=W[j], sum[i][j][0]=S[j], mx[i][j][0]=(1<<(i+1))-1-S[j];
else nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=min(S[j]-1, (1<<(i+1))-1-P[j]);
}
nxt[i][N][0]=N, sum[i][N][0]=0, mx[i][N][0]=(1<<(i+1))-1;
for(int j=1; j<=i; j++) for(int k=0; k<=N; k++) {
nxt[i][k][j]=nxt[i][nxt[i][k][j-1]][j-1];
sum[i][k][j]=sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1];
mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-(int)min((ll)INT_MAX, sum[i][k][j-1]));
}
}
for(int j=0; j<25; j++) for(int k=0; k<=N; k++) mx[24][k][j]=INT_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=i; j>=0; j--) if(vv<=mx[i][kk][j]) {
vv+=sum[i][kk][j], kk=nxt[i][kk][j];
if(kk==N) break;
}
if(kk==N) {
for(int j=i; j>=0; j--) if(nxt[i][k][j]!=N) v+=sum[i][k][j], k=nxt[i][k][j];
if(k!=N) v+=sum[i][k][0], k=nxt[i][k][0];
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:50:1: warning: control reaches end of non-void function [-Wreturn-type]
50 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
206 ms |
710592 KB |
Output is correct |
2 |
Correct |
188 ms |
710604 KB |
Output is correct |
3 |
Correct |
200 ms |
722928 KB |
Output is correct |
4 |
Correct |
1010 ms |
1019992 KB |
Output is correct |
5 |
Correct |
192 ms |
722808 KB |
Output is correct |
6 |
Correct |
1025 ms |
1019928 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
206 ms |
716624 KB |
Output is correct |
2 |
Runtime error |
1477 ms |
2097152 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
716808 KB |
Output is correct |
2 |
Correct |
1284 ms |
1021536 KB |
Output is correct |
3 |
Correct |
1234 ms |
1021424 KB |
Output is correct |
4 |
Correct |
1402 ms |
1020916 KB |
Output is correct |
5 |
Correct |
1321 ms |
1020808 KB |
Output is correct |
6 |
Correct |
1232 ms |
1021264 KB |
Output is correct |
7 |
Correct |
1335 ms |
1021064 KB |
Output is correct |
8 |
Correct |
2103 ms |
1020932 KB |
Output is correct |
9 |
Correct |
969 ms |
1020600 KB |
Output is correct |
10 |
Correct |
1824 ms |
1020684 KB |
Output is correct |
11 |
Correct |
2340 ms |
1021068 KB |
Output is correct |
12 |
Correct |
5239 ms |
1021108 KB |
Output is correct |
13 |
Correct |
5065 ms |
1021064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
716808 KB |
Output is correct |
2 |
Correct |
1284 ms |
1021536 KB |
Output is correct |
3 |
Correct |
1234 ms |
1021424 KB |
Output is correct |
4 |
Correct |
1402 ms |
1020916 KB |
Output is correct |
5 |
Correct |
1321 ms |
1020808 KB |
Output is correct |
6 |
Correct |
1232 ms |
1021264 KB |
Output is correct |
7 |
Correct |
1335 ms |
1021064 KB |
Output is correct |
8 |
Correct |
2103 ms |
1020932 KB |
Output is correct |
9 |
Correct |
969 ms |
1020600 KB |
Output is correct |
10 |
Correct |
1824 ms |
1020684 KB |
Output is correct |
11 |
Correct |
2340 ms |
1021068 KB |
Output is correct |
12 |
Correct |
5239 ms |
1021108 KB |
Output is correct |
13 |
Correct |
5065 ms |
1021064 KB |
Output is correct |
14 |
Correct |
210 ms |
716624 KB |
Output is correct |
15 |
Correct |
1411 ms |
1021196 KB |
Output is correct |
16 |
Correct |
1294 ms |
1021324 KB |
Output is correct |
17 |
Correct |
1884 ms |
1020928 KB |
Output is correct |
18 |
Correct |
1623 ms |
1020936 KB |
Output is correct |
19 |
Correct |
1643 ms |
1021068 KB |
Output is correct |
20 |
Correct |
1650 ms |
1020808 KB |
Output is correct |
21 |
Correct |
1588 ms |
1020936 KB |
Output is correct |
22 |
Correct |
2354 ms |
1020940 KB |
Output is correct |
23 |
Correct |
3086 ms |
1021332 KB |
Output is correct |
24 |
Correct |
3323 ms |
1021068 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
189 ms |
716808 KB |
Output is correct |
2 |
Correct |
1284 ms |
1021536 KB |
Output is correct |
3 |
Correct |
1234 ms |
1021424 KB |
Output is correct |
4 |
Correct |
1402 ms |
1020916 KB |
Output is correct |
5 |
Correct |
1321 ms |
1020808 KB |
Output is correct |
6 |
Correct |
1232 ms |
1021264 KB |
Output is correct |
7 |
Correct |
1335 ms |
1021064 KB |
Output is correct |
8 |
Correct |
2103 ms |
1020932 KB |
Output is correct |
9 |
Correct |
969 ms |
1020600 KB |
Output is correct |
10 |
Correct |
1824 ms |
1020684 KB |
Output is correct |
11 |
Correct |
2340 ms |
1021068 KB |
Output is correct |
12 |
Correct |
5239 ms |
1021108 KB |
Output is correct |
13 |
Correct |
5065 ms |
1021064 KB |
Output is correct |
14 |
Correct |
210 ms |
716624 KB |
Output is correct |
15 |
Correct |
1411 ms |
1021196 KB |
Output is correct |
16 |
Correct |
1294 ms |
1021324 KB |
Output is correct |
17 |
Correct |
1884 ms |
1020928 KB |
Output is correct |
18 |
Correct |
1623 ms |
1020936 KB |
Output is correct |
19 |
Correct |
1643 ms |
1021068 KB |
Output is correct |
20 |
Correct |
1650 ms |
1020808 KB |
Output is correct |
21 |
Correct |
1588 ms |
1020936 KB |
Output is correct |
22 |
Correct |
2354 ms |
1020940 KB |
Output is correct |
23 |
Correct |
3086 ms |
1021332 KB |
Output is correct |
24 |
Correct |
3323 ms |
1021068 KB |
Output is correct |
25 |
Correct |
966 ms |
1020356 KB |
Output is correct |
26 |
Correct |
1267 ms |
1021436 KB |
Output is correct |
27 |
Correct |
1443 ms |
1020812 KB |
Output is correct |
28 |
Correct |
1147 ms |
1020756 KB |
Output is correct |
29 |
Correct |
1433 ms |
1021324 KB |
Output is correct |
30 |
Correct |
1746 ms |
1020944 KB |
Output is correct |
31 |
Correct |
1869 ms |
1020804 KB |
Output is correct |
32 |
Correct |
1872 ms |
1020944 KB |
Output is correct |
33 |
Correct |
1166 ms |
1020752 KB |
Output is correct |
34 |
Correct |
2263 ms |
1020816 KB |
Output is correct |
35 |
Correct |
1711 ms |
1021308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
206 ms |
716624 KB |
Output is correct |
2 |
Runtime error |
1477 ms |
2097152 KB |
Execution killed with signal 9 |
3 |
Halted |
0 ms |
0 KB |
- |