#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int S = 4, T = 12, L = 24, L2 = 20, MX = 400002, INF = 1e9+100;
struct Node{
int s, c, val;
Node(){}
Node(int _s, int _c, int _v): s(_s), c(_c), val(_v) {}
Node operator + (const Node &S) const{
assert((ll)c + S.c <= INF);
return Node(S.s, c+S.c, min(val, S.val-c));
}
}sp1[L][T][MX];
pair<int, ll> sp2[L2][MX];
int n;
pair<int, ll> operator + (const pair<int, ll> &a, const pair<int, ll> &b){return {b.first, a.second+b.second};}
vector<int> is, ip, iw, il;
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
is = s, ip = p, iw = w, il = l;
n = N;
for (int i=0;i<L;i++){
for (int v=0;v<n;v++){
if (s[v]<=(1<<i)) sp1[i][0][v] = Node(w[v], s[v], INF);
else sp1[i][0][v] = Node(l[v], p[v], s[v]);
}
for (int j=1;j<T;j++){
for (int v=0;v<n;v++){
sp1[i][j][v] = sp1[i][j-1][v];
if (sp1[i][j-1][v].s==n || sp1[i][j-1][v].c >= (1<<i)) continue;
for (int t=0;t<S-1;t++){
int cur = sp1[i][j][v].s;
sp1[i][j][v] = sp1[i][j][v] + sp1[i][j-1][cur];
if (sp1[i][j][v].s==n || sp1[i][j][v].c >= (1<<i)) break;
}
}
}
}
for (int v=0;v<n;v++) sp2[0][v] = {w[v], s[v]};
for (int j=1;j<L2;j++){
for (int v=0;v<n;v++){
sp2[j][v] = sp2[j-1][v];
if (sp2[j][v].first==n) continue;
sp2[j][v] = sp2[j][v] + sp2[j-1][sp2[j-1][v].first];
}
}
}
long long simulate(int pos, int mp0) {
ll mp = mp0;
for (int i=0;i<L;i++){
if (mp >= (1<<(i+1))) continue;
Node cur(pos, 0, INF);
for (int j=T-1;j>=0;j--){
int loop = 0;
while(true){
assert(++loop <= S+2);
Node nxt = cur + sp1[i][j][cur.s];
if (nxt.s == n || nxt.c >= ((1<<(i+1))-mp) || mp >= nxt.val) break;
cur = nxt;
}
}
pos = cur.s;
mp += cur.c;
assert(pos!=n && mp < (1<<(i+1)));
if (mp >= is[pos]){mp += is[pos]; pos = iw[pos];}
else {mp += ip[pos]; pos = il[pos];}
if (pos==n) return mp;
assert(mp >= (1<<(i+1)));
}
for (int j=L2-1;j>=0;j--) if (sp2[j][pos].first!=n){
mp += sp2[j][pos].second;
pos = sp2[j][pos].first;
}
assert(pos!=n);
assert(sp2[0][pos].first==n);
return mp + sp2[0][pos].second;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2772 KB |
Output is correct |
2 |
Correct |
2 ms |
2772 KB |
Output is correct |
3 |
Correct |
7 ms |
10196 KB |
Output is correct |
4 |
Correct |
132 ms |
190792 KB |
Output is correct |
5 |
Correct |
7 ms |
10196 KB |
Output is correct |
6 |
Correct |
163 ms |
190660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
1519 ms |
1499704 KB |
Output is correct |
3 |
Correct |
1670 ms |
1499208 KB |
Output is correct |
4 |
Correct |
1546 ms |
1498700 KB |
Output is correct |
5 |
Correct |
1281 ms |
1498840 KB |
Output is correct |
6 |
Correct |
3117 ms |
1498696 KB |
Output is correct |
7 |
Correct |
3049 ms |
1498784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
235 ms |
190964 KB |
Output is correct |
3 |
Correct |
189 ms |
190984 KB |
Output is correct |
4 |
Correct |
216 ms |
190952 KB |
Output is correct |
5 |
Correct |
352 ms |
190936 KB |
Output is correct |
6 |
Correct |
524 ms |
190944 KB |
Output is correct |
7 |
Correct |
635 ms |
191048 KB |
Output is correct |
8 |
Correct |
623 ms |
190944 KB |
Output is correct |
9 |
Correct |
198 ms |
191000 KB |
Output is correct |
10 |
Correct |
807 ms |
190992 KB |
Output is correct |
11 |
Correct |
1387 ms |
191004 KB |
Output is correct |
12 |
Correct |
2649 ms |
190924 KB |
Output is correct |
13 |
Correct |
2268 ms |
190908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
235 ms |
190964 KB |
Output is correct |
3 |
Correct |
189 ms |
190984 KB |
Output is correct |
4 |
Correct |
216 ms |
190952 KB |
Output is correct |
5 |
Correct |
352 ms |
190936 KB |
Output is correct |
6 |
Correct |
524 ms |
190944 KB |
Output is correct |
7 |
Correct |
635 ms |
191048 KB |
Output is correct |
8 |
Correct |
623 ms |
190944 KB |
Output is correct |
9 |
Correct |
198 ms |
191000 KB |
Output is correct |
10 |
Correct |
807 ms |
190992 KB |
Output is correct |
11 |
Correct |
1387 ms |
191004 KB |
Output is correct |
12 |
Correct |
2649 ms |
190924 KB |
Output is correct |
13 |
Correct |
2268 ms |
190908 KB |
Output is correct |
14 |
Correct |
11 ms |
6540 KB |
Output is correct |
15 |
Correct |
181 ms |
190920 KB |
Output is correct |
16 |
Correct |
168 ms |
190908 KB |
Output is correct |
17 |
Correct |
283 ms |
190908 KB |
Output is correct |
18 |
Correct |
317 ms |
190892 KB |
Output is correct |
19 |
Correct |
571 ms |
190924 KB |
Output is correct |
20 |
Correct |
460 ms |
190984 KB |
Output is correct |
21 |
Correct |
549 ms |
190928 KB |
Output is correct |
22 |
Correct |
756 ms |
191000 KB |
Output is correct |
23 |
Correct |
1394 ms |
190920 KB |
Output is correct |
24 |
Correct |
1278 ms |
190996 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
235 ms |
190964 KB |
Output is correct |
3 |
Correct |
189 ms |
190984 KB |
Output is correct |
4 |
Correct |
216 ms |
190952 KB |
Output is correct |
5 |
Correct |
352 ms |
190936 KB |
Output is correct |
6 |
Correct |
524 ms |
190944 KB |
Output is correct |
7 |
Correct |
635 ms |
191048 KB |
Output is correct |
8 |
Correct |
623 ms |
190944 KB |
Output is correct |
9 |
Correct |
198 ms |
191000 KB |
Output is correct |
10 |
Correct |
807 ms |
190992 KB |
Output is correct |
11 |
Correct |
1387 ms |
191004 KB |
Output is correct |
12 |
Correct |
2649 ms |
190924 KB |
Output is correct |
13 |
Correct |
2268 ms |
190908 KB |
Output is correct |
14 |
Correct |
11 ms |
6540 KB |
Output is correct |
15 |
Correct |
181 ms |
190920 KB |
Output is correct |
16 |
Correct |
168 ms |
190908 KB |
Output is correct |
17 |
Correct |
283 ms |
190908 KB |
Output is correct |
18 |
Correct |
317 ms |
190892 KB |
Output is correct |
19 |
Correct |
571 ms |
190924 KB |
Output is correct |
20 |
Correct |
460 ms |
190984 KB |
Output is correct |
21 |
Correct |
549 ms |
190928 KB |
Output is correct |
22 |
Correct |
756 ms |
191000 KB |
Output is correct |
23 |
Correct |
1394 ms |
190920 KB |
Output is correct |
24 |
Correct |
1278 ms |
190996 KB |
Output is correct |
25 |
Correct |
122 ms |
190244 KB |
Output is correct |
26 |
Correct |
185 ms |
191012 KB |
Output is correct |
27 |
Correct |
237 ms |
190924 KB |
Output is correct |
28 |
Correct |
217 ms |
190924 KB |
Output is correct |
29 |
Correct |
196 ms |
190940 KB |
Output is correct |
30 |
Correct |
490 ms |
190932 KB |
Output is correct |
31 |
Correct |
646 ms |
191012 KB |
Output is correct |
32 |
Correct |
833 ms |
190908 KB |
Output is correct |
33 |
Correct |
810 ms |
190924 KB |
Output is correct |
34 |
Correct |
1381 ms |
190948 KB |
Output is correct |
35 |
Correct |
868 ms |
191036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
6484 KB |
Output is correct |
2 |
Correct |
1519 ms |
1499704 KB |
Output is correct |
3 |
Correct |
1670 ms |
1499208 KB |
Output is correct |
4 |
Correct |
1546 ms |
1498700 KB |
Output is correct |
5 |
Correct |
1281 ms |
1498840 KB |
Output is correct |
6 |
Correct |
3117 ms |
1498696 KB |
Output is correct |
7 |
Correct |
3049 ms |
1498784 KB |
Output is correct |
8 |
Correct |
4 ms |
6484 KB |
Output is correct |
9 |
Correct |
235 ms |
190964 KB |
Output is correct |
10 |
Correct |
189 ms |
190984 KB |
Output is correct |
11 |
Correct |
216 ms |
190952 KB |
Output is correct |
12 |
Correct |
352 ms |
190936 KB |
Output is correct |
13 |
Correct |
524 ms |
190944 KB |
Output is correct |
14 |
Correct |
635 ms |
191048 KB |
Output is correct |
15 |
Correct |
623 ms |
190944 KB |
Output is correct |
16 |
Correct |
198 ms |
191000 KB |
Output is correct |
17 |
Correct |
807 ms |
190992 KB |
Output is correct |
18 |
Correct |
1387 ms |
191004 KB |
Output is correct |
19 |
Correct |
2649 ms |
190924 KB |
Output is correct |
20 |
Correct |
2268 ms |
190908 KB |
Output is correct |
21 |
Correct |
11 ms |
6540 KB |
Output is correct |
22 |
Correct |
181 ms |
190920 KB |
Output is correct |
23 |
Correct |
168 ms |
190908 KB |
Output is correct |
24 |
Correct |
283 ms |
190908 KB |
Output is correct |
25 |
Correct |
317 ms |
190892 KB |
Output is correct |
26 |
Correct |
571 ms |
190924 KB |
Output is correct |
27 |
Correct |
460 ms |
190984 KB |
Output is correct |
28 |
Correct |
549 ms |
190928 KB |
Output is correct |
29 |
Correct |
756 ms |
191000 KB |
Output is correct |
30 |
Correct |
1394 ms |
190920 KB |
Output is correct |
31 |
Correct |
1278 ms |
190996 KB |
Output is correct |
32 |
Correct |
122 ms |
190244 KB |
Output is correct |
33 |
Correct |
185 ms |
191012 KB |
Output is correct |
34 |
Correct |
237 ms |
190924 KB |
Output is correct |
35 |
Correct |
217 ms |
190924 KB |
Output is correct |
36 |
Correct |
196 ms |
190940 KB |
Output is correct |
37 |
Correct |
490 ms |
190932 KB |
Output is correct |
38 |
Correct |
646 ms |
191012 KB |
Output is correct |
39 |
Correct |
833 ms |
190908 KB |
Output is correct |
40 |
Correct |
810 ms |
190924 KB |
Output is correct |
41 |
Correct |
1381 ms |
190948 KB |
Output is correct |
42 |
Correct |
868 ms |
191036 KB |
Output is correct |
43 |
Correct |
1 ms |
2772 KB |
Output is correct |
44 |
Correct |
4 ms |
6516 KB |
Output is correct |
45 |
Correct |
895 ms |
1498508 KB |
Output is correct |
46 |
Correct |
1452 ms |
1498752 KB |
Output is correct |
47 |
Correct |
1491 ms |
1498832 KB |
Output is correct |
48 |
Correct |
1403 ms |
1498540 KB |
Output is correct |
49 |
Correct |
912 ms |
1498504 KB |
Output is correct |
50 |
Correct |
1856 ms |
1498908 KB |
Output is correct |
51 |
Correct |
1406 ms |
1498468 KB |
Output is correct |
52 |
Correct |
1980 ms |
1498432 KB |
Output is correct |
53 |
Correct |
2993 ms |
1497712 KB |
Output is correct |
54 |
Correct |
2117 ms |
1497676 KB |
Output is correct |
55 |
Correct |
2688 ms |
1497772 KB |
Output is correct |
56 |
Correct |
2894 ms |
1497784 KB |
Output is correct |
57 |
Correct |
2933 ms |
1497656 KB |
Output is correct |
58 |
Correct |
3376 ms |
1497780 KB |
Output is correct |
59 |
Correct |
2985 ms |
1497656 KB |
Output is correct |
60 |
Correct |
2157 ms |
1497696 KB |
Output is correct |
61 |
Correct |
2024 ms |
1497740 KB |
Output is correct |