#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
uint binary[12][400001][26][2];//index, +, max excluded
ull binary_add[12][400001][26];
uint safe_sub(uint a, ull b) {
if (a >= b)
return a - b;
return 0;
}
int N;
vector<int> S, P, W, L;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
n++;
N = n;
S = s, P = p, W = w, L = l;
for (int range = 0; range < 12; range++)
{
ll r = 1 << (range + 13);
for (int i = 0; i < n; i++)
{
if (s[i] <= r) {
binary[range][i][0][0] = w[i];
binary_add[range][i][0] = s[i];
binary[range][i][0][1] = UINT_MAX;
} else {
binary[range][i][0][0] = l[i];
binary_add[range][i][0] = p[i];
binary[range][i][0][1] = s[i];
}
}
for (int i = 1; i < 26; i++)
{
for (int ind = 0; ind < n; ind++)
{
int pointer = binary[range][ind][i - 1][0];
binary[range][ind][i][0] = binary[range][pointer][i - 1][0];
binary_add[range][ind][i] = binary_add[range][ind][i - 1] + binary_add[range][pointer][i - 1];
binary[range][ind][i][1] = min(binary[range][ind][i - 1][1], safe_sub(binary[range][pointer][i - 1][1], binary_add[range][ind][i - 1]));
}
}
}
}
long long simulate(int x, int z) {
ll t = z;
while (t < 8192 && x != N - 1) {
if (t >= S[x]) {
t += S[x];
x = W[x];
} else {
t += P[x];
x = L[x];
}
}
for (int r = 0; r < 12; r++)
{
for (int s = 25; s >= 0; s--)
{
while (binary[r][x][s][1] > t && x != N - 1) {
t += binary_add[r][x][s];
x = binary[r][x][s][0];
}
}
}
return t + binary_add[11][x][25];
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
7 ms |
10324 KB |
Output is correct |
4 |
Correct |
255 ms |
248160 KB |
Output is correct |
5 |
Correct |
7 ms |
10324 KB |
Output is correct |
6 |
Correct |
213 ms |
247984 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
3407 ms |
1980608 KB |
Output is correct |
3 |
Correct |
3029 ms |
1980608 KB |
Output is correct |
4 |
Correct |
3217 ms |
1982144 KB |
Output is correct |
5 |
Correct |
2859 ms |
1980964 KB |
Output is correct |
6 |
Correct |
3639 ms |
1978112 KB |
Output is correct |
7 |
Correct |
3687 ms |
1976600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
358 ms |
248548 KB |
Output is correct |
3 |
Correct |
433 ms |
248712 KB |
Output is correct |
4 |
Correct |
266 ms |
247748 KB |
Output is correct |
5 |
Correct |
248 ms |
247924 KB |
Output is correct |
6 |
Correct |
312 ms |
247800 KB |
Output is correct |
7 |
Correct |
784 ms |
247816 KB |
Output is correct |
8 |
Correct |
292 ms |
247820 KB |
Output is correct |
9 |
Correct |
258 ms |
247740 KB |
Output is correct |
10 |
Correct |
450 ms |
247824 KB |
Output is correct |
11 |
Correct |
3500 ms |
247800 KB |
Output is correct |
12 |
Correct |
3822 ms |
247832 KB |
Output is correct |
13 |
Correct |
1453 ms |
247744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
358 ms |
248548 KB |
Output is correct |
3 |
Correct |
433 ms |
248712 KB |
Output is correct |
4 |
Correct |
266 ms |
247748 KB |
Output is correct |
5 |
Correct |
248 ms |
247924 KB |
Output is correct |
6 |
Correct |
312 ms |
247800 KB |
Output is correct |
7 |
Correct |
784 ms |
247816 KB |
Output is correct |
8 |
Correct |
292 ms |
247820 KB |
Output is correct |
9 |
Correct |
258 ms |
247740 KB |
Output is correct |
10 |
Correct |
450 ms |
247824 KB |
Output is correct |
11 |
Correct |
3500 ms |
247800 KB |
Output is correct |
12 |
Correct |
3822 ms |
247832 KB |
Output is correct |
13 |
Correct |
1453 ms |
247744 KB |
Output is correct |
14 |
Correct |
5 ms |
5460 KB |
Output is correct |
15 |
Correct |
343 ms |
247852 KB |
Output is correct |
16 |
Correct |
373 ms |
247852 KB |
Output is correct |
17 |
Correct |
329 ms |
247852 KB |
Output is correct |
18 |
Correct |
285 ms |
247768 KB |
Output is correct |
19 |
Correct |
409 ms |
247816 KB |
Output is correct |
20 |
Correct |
420 ms |
247780 KB |
Output is correct |
21 |
Correct |
279 ms |
247820 KB |
Output is correct |
22 |
Correct |
1359 ms |
247768 KB |
Output is correct |
23 |
Correct |
3344 ms |
247836 KB |
Output is correct |
24 |
Correct |
2001 ms |
247804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
358 ms |
248548 KB |
Output is correct |
3 |
Correct |
433 ms |
248712 KB |
Output is correct |
4 |
Correct |
266 ms |
247748 KB |
Output is correct |
5 |
Correct |
248 ms |
247924 KB |
Output is correct |
6 |
Correct |
312 ms |
247800 KB |
Output is correct |
7 |
Correct |
784 ms |
247816 KB |
Output is correct |
8 |
Correct |
292 ms |
247820 KB |
Output is correct |
9 |
Correct |
258 ms |
247740 KB |
Output is correct |
10 |
Correct |
450 ms |
247824 KB |
Output is correct |
11 |
Correct |
3500 ms |
247800 KB |
Output is correct |
12 |
Correct |
3822 ms |
247832 KB |
Output is correct |
13 |
Correct |
1453 ms |
247744 KB |
Output is correct |
14 |
Correct |
5 ms |
5460 KB |
Output is correct |
15 |
Correct |
343 ms |
247852 KB |
Output is correct |
16 |
Correct |
373 ms |
247852 KB |
Output is correct |
17 |
Correct |
329 ms |
247852 KB |
Output is correct |
18 |
Correct |
285 ms |
247768 KB |
Output is correct |
19 |
Correct |
409 ms |
247816 KB |
Output is correct |
20 |
Correct |
420 ms |
247780 KB |
Output is correct |
21 |
Correct |
279 ms |
247820 KB |
Output is correct |
22 |
Correct |
1359 ms |
247768 KB |
Output is correct |
23 |
Correct |
3344 ms |
247836 KB |
Output is correct |
24 |
Correct |
2001 ms |
247804 KB |
Output is correct |
25 |
Correct |
257 ms |
247016 KB |
Output is correct |
26 |
Correct |
397 ms |
247768 KB |
Output is correct |
27 |
Correct |
292 ms |
247744 KB |
Output is correct |
28 |
Correct |
297 ms |
247828 KB |
Output is correct |
29 |
Correct |
380 ms |
247800 KB |
Output is correct |
30 |
Correct |
339 ms |
247740 KB |
Output is correct |
31 |
Correct |
351 ms |
247784 KB |
Output is correct |
32 |
Correct |
1094 ms |
247840 KB |
Output is correct |
33 |
Correct |
325 ms |
247748 KB |
Output is correct |
34 |
Correct |
701 ms |
247624 KB |
Output is correct |
35 |
Correct |
427 ms |
247868 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5460 KB |
Output is correct |
2 |
Correct |
3407 ms |
1980608 KB |
Output is correct |
3 |
Correct |
3029 ms |
1980608 KB |
Output is correct |
4 |
Correct |
3217 ms |
1982144 KB |
Output is correct |
5 |
Correct |
2859 ms |
1980964 KB |
Output is correct |
6 |
Correct |
3639 ms |
1978112 KB |
Output is correct |
7 |
Correct |
3687 ms |
1976600 KB |
Output is correct |
8 |
Correct |
4 ms |
5460 KB |
Output is correct |
9 |
Correct |
358 ms |
248548 KB |
Output is correct |
10 |
Correct |
433 ms |
248712 KB |
Output is correct |
11 |
Correct |
266 ms |
247748 KB |
Output is correct |
12 |
Correct |
248 ms |
247924 KB |
Output is correct |
13 |
Correct |
312 ms |
247800 KB |
Output is correct |
14 |
Correct |
784 ms |
247816 KB |
Output is correct |
15 |
Correct |
292 ms |
247820 KB |
Output is correct |
16 |
Correct |
258 ms |
247740 KB |
Output is correct |
17 |
Correct |
450 ms |
247824 KB |
Output is correct |
18 |
Correct |
3500 ms |
247800 KB |
Output is correct |
19 |
Correct |
3822 ms |
247832 KB |
Output is correct |
20 |
Correct |
1453 ms |
247744 KB |
Output is correct |
21 |
Correct |
5 ms |
5460 KB |
Output is correct |
22 |
Correct |
343 ms |
247852 KB |
Output is correct |
23 |
Correct |
373 ms |
247852 KB |
Output is correct |
24 |
Correct |
329 ms |
247852 KB |
Output is correct |
25 |
Correct |
285 ms |
247768 KB |
Output is correct |
26 |
Correct |
409 ms |
247816 KB |
Output is correct |
27 |
Correct |
420 ms |
247780 KB |
Output is correct |
28 |
Correct |
279 ms |
247820 KB |
Output is correct |
29 |
Correct |
1359 ms |
247768 KB |
Output is correct |
30 |
Correct |
3344 ms |
247836 KB |
Output is correct |
31 |
Correct |
2001 ms |
247804 KB |
Output is correct |
32 |
Correct |
257 ms |
247016 KB |
Output is correct |
33 |
Correct |
397 ms |
247768 KB |
Output is correct |
34 |
Correct |
292 ms |
247744 KB |
Output is correct |
35 |
Correct |
297 ms |
247828 KB |
Output is correct |
36 |
Correct |
380 ms |
247800 KB |
Output is correct |
37 |
Correct |
339 ms |
247740 KB |
Output is correct |
38 |
Correct |
351 ms |
247784 KB |
Output is correct |
39 |
Correct |
1094 ms |
247840 KB |
Output is correct |
40 |
Correct |
325 ms |
247748 KB |
Output is correct |
41 |
Correct |
701 ms |
247624 KB |
Output is correct |
42 |
Correct |
427 ms |
247868 KB |
Output is correct |
43 |
Correct |
1 ms |
468 KB |
Output is correct |
44 |
Correct |
4 ms |
5460 KB |
Output is correct |
45 |
Correct |
3450 ms |
1985344 KB |
Output is correct |
46 |
Correct |
2972 ms |
1980736 KB |
Output is correct |
47 |
Correct |
3586 ms |
1981024 KB |
Output is correct |
48 |
Correct |
2882 ms |
1983424 KB |
Output is correct |
49 |
Correct |
3300 ms |
1985348 KB |
Output is correct |
50 |
Correct |
3412 ms |
1982912 KB |
Output is correct |
51 |
Correct |
2842 ms |
1983292 KB |
Output is correct |
52 |
Correct |
3330 ms |
1981024 KB |
Output is correct |
53 |
Correct |
5239 ms |
1981844 KB |
Output is correct |
54 |
Correct |
3296 ms |
1982920 KB |
Output is correct |
55 |
Correct |
3711 ms |
1981932 KB |
Output is correct |
56 |
Correct |
3988 ms |
1982532 KB |
Output is correct |
57 |
Correct |
3633 ms |
1982604 KB |
Output is correct |
58 |
Correct |
3691 ms |
1982648 KB |
Output is correct |
59 |
Correct |
3783 ms |
1982784 KB |
Output is correct |
60 |
Correct |
4718 ms |
1982016 KB |
Output is correct |
61 |
Correct |
4526 ms |
1982008 KB |
Output is correct |