#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 55000
int N, P[maxn], L[maxn], S[maxn], W[maxn];
pair<int,int> nx[maxn][10][32];
vector<int> st;
int tp;
pair<int,int> nxt(int u, int qtd, int id) {
int val = 0;
for(int pt = 30; pt >= 0; pt--) {
if(qtd >= (1<<pt)) {
qtd-= (1<<pt);
val+= nx[u][id][pt].sc;
u = nx[u][id][pt].fr;
}
}
return mp(u,val);
}
int simulate(int32_t x, int32_t z) {
int zz = z;
if(tp == 0) {
int id = 0;
while(zz >= st[id]) id++;
id--;
while(x != N) {
// cout << x << " " << zz << " " << id << endl;
int l = 0;
int r = 1e7 + 10;
pair<int,int> ans1;
while(l <= r) {
int mid = (l+r)>>1;
auto aux = nxt(x,mid,id);
if(zz+aux.sc >= st[id+1] || aux.fr == N) {
ans1 = aux;
ans1.sc+= zz;
r = mid-1;
}
else {
l = mid+1;
}
}
x = ans1.fr;
zz = ans1.sc;
id++;
}
}
else {
while(x != N) {
if(S[x] <= zz) {
//ganhou
zz+= S[x];
x = W[x];
}
else {
//perdeu
zz+= P[x];
x = L[x];
}
}
}
return zz;
}
void init(int32_t n, vector<int32_t> s, vector<int32_t> p, vector<int32_t> w, vector<int32_t> l) {
N = n;
st.pb(0);
st.pb(inf);
for(int i = 0; i < n; i++) {
st.pb(s[i]);
}
sort(all(st));
st.erase(unique(all(st)),st.end());
if(st.size() <= 8) {
tp = 0;
for(int i = 0; i < st.size(); i++) {
for(int j = 0; j < n; j++) {
if(s[j] <= st[i]) {
nx[j][i][0] = mp(w[j],s[j]);
}
else {
nx[j][i][0] = mp(l[j],p[j]);
}
}
for(int pt = 0; pt <= 30; pt++) {
nx[n][i][pt].fr = n;
nx[n][i][pt].sc = 0;
}
for(int pt = 1; pt <= 30; pt++) {
for(int j = 0; j < n; j++) {
nx[j][i][pt].fr = nx[nx[j][i][pt-1].fr][i][pt-1].fr;
nx[j][i][pt].sc = nx[j][i][pt-1].sc + nx[nx[j][i][pt-1].fr][i][pt-1].sc;
}
}
}
}
else {
tp = 1;
for(int i = 0; i < n; i++) {
S[i] = s[i];
W[i] = w[i];
L[i] = l[i];
P[i] = p[i];
}
}
}
Compilation message
dungeons.cpp: In function 'void init(int32_t, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:97:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int i = 0; i < st.size(); i++) {
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
20 ms |
4904 KB |
Output is correct |
5 |
Correct |
1 ms |
460 KB |
Output is correct |
6 |
Correct |
20 ms |
4776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Runtime error |
168 ms |
39092 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5324 KB |
Output is correct |
2 |
Correct |
287 ms |
253560 KB |
Output is correct |
3 |
Correct |
369 ms |
253600 KB |
Output is correct |
4 |
Correct |
337 ms |
253648 KB |
Output is correct |
5 |
Correct |
330 ms |
253756 KB |
Output is correct |
6 |
Correct |
306 ms |
253628 KB |
Output is correct |
7 |
Correct |
315 ms |
253600 KB |
Output is correct |
8 |
Correct |
343 ms |
253660 KB |
Output is correct |
9 |
Correct |
251 ms |
253628 KB |
Output is correct |
10 |
Correct |
340 ms |
253816 KB |
Output is correct |
11 |
Correct |
344 ms |
253668 KB |
Output is correct |
12 |
Correct |
875 ms |
253580 KB |
Output is correct |
13 |
Correct |
852 ms |
253752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5324 KB |
Output is correct |
2 |
Correct |
287 ms |
253560 KB |
Output is correct |
3 |
Correct |
369 ms |
253600 KB |
Output is correct |
4 |
Correct |
337 ms |
253648 KB |
Output is correct |
5 |
Correct |
330 ms |
253756 KB |
Output is correct |
6 |
Correct |
306 ms |
253628 KB |
Output is correct |
7 |
Correct |
315 ms |
253600 KB |
Output is correct |
8 |
Correct |
343 ms |
253660 KB |
Output is correct |
9 |
Correct |
251 ms |
253628 KB |
Output is correct |
10 |
Correct |
340 ms |
253816 KB |
Output is correct |
11 |
Correct |
344 ms |
253668 KB |
Output is correct |
12 |
Correct |
875 ms |
253580 KB |
Output is correct |
13 |
Correct |
852 ms |
253752 KB |
Output is correct |
14 |
Correct |
6 ms |
5324 KB |
Output is correct |
15 |
Correct |
339 ms |
253656 KB |
Output is correct |
16 |
Correct |
416 ms |
253664 KB |
Output is correct |
17 |
Correct |
479 ms |
253640 KB |
Output is correct |
18 |
Correct |
699 ms |
253648 KB |
Output is correct |
19 |
Correct |
612 ms |
253648 KB |
Output is correct |
20 |
Correct |
624 ms |
253628 KB |
Output is correct |
21 |
Correct |
749 ms |
253636 KB |
Output is correct |
22 |
Correct |
532 ms |
253756 KB |
Output is correct |
23 |
Correct |
618 ms |
253756 KB |
Output is correct |
24 |
Correct |
1043 ms |
253632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
5324 KB |
Output is correct |
2 |
Correct |
287 ms |
253560 KB |
Output is correct |
3 |
Correct |
369 ms |
253600 KB |
Output is correct |
4 |
Correct |
337 ms |
253648 KB |
Output is correct |
5 |
Correct |
330 ms |
253756 KB |
Output is correct |
6 |
Correct |
306 ms |
253628 KB |
Output is correct |
7 |
Correct |
315 ms |
253600 KB |
Output is correct |
8 |
Correct |
343 ms |
253660 KB |
Output is correct |
9 |
Correct |
251 ms |
253628 KB |
Output is correct |
10 |
Correct |
340 ms |
253816 KB |
Output is correct |
11 |
Correct |
344 ms |
253668 KB |
Output is correct |
12 |
Correct |
875 ms |
253580 KB |
Output is correct |
13 |
Correct |
852 ms |
253752 KB |
Output is correct |
14 |
Correct |
6 ms |
5324 KB |
Output is correct |
15 |
Correct |
339 ms |
253656 KB |
Output is correct |
16 |
Correct |
416 ms |
253664 KB |
Output is correct |
17 |
Correct |
479 ms |
253640 KB |
Output is correct |
18 |
Correct |
699 ms |
253648 KB |
Output is correct |
19 |
Correct |
612 ms |
253648 KB |
Output is correct |
20 |
Correct |
624 ms |
253628 KB |
Output is correct |
21 |
Correct |
749 ms |
253636 KB |
Output is correct |
22 |
Correct |
532 ms |
253756 KB |
Output is correct |
23 |
Correct |
618 ms |
253756 KB |
Output is correct |
24 |
Correct |
1043 ms |
253632 KB |
Output is correct |
25 |
Correct |
22 ms |
3932 KB |
Output is correct |
26 |
Correct |
46 ms |
6428 KB |
Output is correct |
27 |
Correct |
39 ms |
5784 KB |
Output is correct |
28 |
Correct |
394 ms |
5836 KB |
Output is correct |
29 |
Correct |
44 ms |
6184 KB |
Output is correct |
30 |
Execution timed out |
7008 ms |
5948 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Runtime error |
168 ms |
39092 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |