| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 745306 | arthur_nascimento | Dungeons Game (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define lg 25
#define maxn 300300
#define inf (1e9)
#define debug
#define ll long long
int jmp[lg][19][maxn];
ll inc[lg][19][maxn];
int least[lg][19][maxn];
vector<int> strength, inc_lose, go_win, go_lose;
int n;
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
//for(int i=0;i<N;i++) if(s[i] != 642842 ) printf("! %d -> %d %d, %d %d\n",i,w[i],l[i],s[i],p[i]);
n = N;
strength = s;
inc_lose = p;
go_win = w;
go_lose = l;
strength.pb(0);
inc_lose.pb(0);
go_win.pb(n);
go_lose.pb(n);
debug("ini!\n");
for(int k=0;k<lg;k++){
for(int i=0;i<n;i++){
if(strength[i] <= (1<<k))
jmp[k][0][i] = go_win[i],
inc[k][0][i] = strength[i],
least[k][0][i] = inf;
else
jmp[k][0][i] = go_lose[i],
inc[k][0][i] = inc_lose[i],
least[k][0][i] = strength[i];
if(k == 0)
debug("%d -> %d\n",i,jmp[k][0][i]);
if(jmp[k][0][i] == n)
least[k][0][i] = -1;
}
for(int j=1;j<19;j++)
for(int i=0;i<n;i++){
jmp[k][j][i] = jmp[k][j-1][jmp[k][j-1][i]],
inc[k][j][i] = inc[k][j-1][i] + inc[k][j-1][ jmp[k][j-1][i] ] ,
least[k][j][i] = max(0ll, min( (ll)least[k][j-1][i], least[k][j-1][ jmp[k][j-1][i] ] - inc[k][j-1][i] ));
if(least[k][j-1][i] > 1e8 && least[k][j-1][ jmp[k][j-1][i] ] > 1e8)
least[k][j][i] = 1e9;
}
}
return;
}
long long simulate(int x, int z0) {
ll z = z0;
while(x < n){
ll aux = z;
int k = 0;
while(aux > 1)
aux /= 2, k++;
k = min(k,24);
debug("x %d z %d k %d\n",x,z,k);
//for(int i=0;i<n;i++)
//debug("k %d i %d -> %d\n",k,i,jmp[k][0][i]);
debug("\n");
for(int j=18;j>=0;j--)
if(least[k][j][x] > z || least[k][j][x] > 1e8){
z += inc[k][j][x];
debug("%d jmp %d to %d add %d\n",x,1<<j,jmp[k][j][x],inc[k][j][x]);
x = jmp[k][j][x];
}
debug("z %d x %d stx %d\n",z,x,strength[x]);
// assert(z >= strength[x]);
//if(!((strength[x] >= (1<<k) || go_win[x] == n))) return 0;
if(z >= strength[x])
z += strength[x],
x = go_win[x];
else
z += inc_lose[x],
x = go_lose[x];
}
//printf("ans %d\n",z);
return z;
}