| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 826564 | arnold518 | 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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 4e5;
const ll INF = 1e18;
int N;
int S[MAXN+10], P[MAXN+10], W[MAXN+10], L[MAXN+10];
int A[25][25][MAXN+10], B[25][25][MAXN+10], C[25][25][MAXN+10];
ll D[MAXN+10];
void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L)
{
N=_N;
for(int i=1; i<=N; i++)
{
S[i]=_S[i-1]; P[i]=_P[i-1];
W[i]=_W[i-1]+1; L[i]=_L[i-1]+1;
}
for(int i=0; i<=23; i++)
{
for(int j=1; j<=N; j++)
{
if(S[j]<(1<<i)) A[i][0][j]=S[j], B[i][0][j]=(1<<(i+1)), C[i][0][j]=W[j];
else if(S[j]<(1<<(i+1))) A[i][0][j]=P[j], B[i][0][j]=min((1<<(i+1)), S[j]), C[i][0][j]=L[j];
else A[i][0][j]=P[j], B[i][0][j]=(1<<(i+1)), C[i][0][j]=L[j];
}
A[i][0][N+1]=0, B[i][0][N+1]=0; C[i][0][N+1]=N+1;
for(int j=1; j<=24; j++)
{
for(int k=1; k<=N+1; k++)
{
C[i][j][k]=C[i][j-1][C[i][j-1][k]];
A[i][j][k]=A[i][j-1][k]+A[i][j-1][C[i][j-1][k]];
B[i][j][k]=min(B[i][j-1][k], B[i][j-1][C[i][j-1][k]]-A[i][j-1][k]);
}
}
}
for(int i=N; i>=0; i--) D[i]=D[W[i]]+S[i];
}
ll simulate(int now, int _x)
{
now++;
ll x=_x;
for(int i=0; i<=23; i++)
{
if(x>=(1<<(i+1))) continue;
for(int j=24; j>=0; j--)
{
if(x<B[i][j][now])
{
x+=A[i][j][now];
now=C[i][j][now];
}
}
if(now>N) break;
if(x<(1<<(i+1)))
{
if(x>=S[now]) x+=S[now], now=W[now];
else x+=P[now], now=L[now];
}
assert(x>=(1<<(i+1)));
}
return x+D[now];
}