| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 457902 | blue | 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 <iostream>
#include <cassert>
using namespace std;
const int maxN = 300'000;
const int lgN = 20;
const int lgS = 25;
//
int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;
//
int nxt[maxN + 1][lgS][lgN]; //dungeon
long long gain[maxN + 1][lgS][lgN];
long long min_change[maxN + 1][lgS][lgN]; //minimum start to end up in different magnitude.
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;
S = s;
P = p;
W = w;
L = l;
for(int i = 0; i <= N; i++)
{
for(int k = 0; k < lgS; k++)
{
if(s[i] < (1 << k))
{
nxt[i][k][0] = w[i];
gain[i][k][0] = s[i];
min_change[i][k][0] = (1 << (k+1)) - gain[i][k][0];
}
else if((1 << k) <= s[i] && s[i] < (1 << (k+1)))
{
nxt[i][k][0] = l[i];
gain[i][k][0] = p[i];
if(s[i] <= p[i])
min_change[i][k][0] = 0;
else
min_change[i][k][0] = (1 << (k+1)) - s[i];
//case 1: s[i] <= p[i]
//min_change = 0
//case 2: p[i] < s[i]
// if(z < p[i]), min_change = 0
// if(p[i] <= z < s[i]), min_change = 2^(k+1) - p[i]
// if(s[i] <= z), min_change = 2^(k+1) - s[i]
}
else
{
nxt[i][k][0] = l[i];
gain[i][k][0] = p[i];
min_change[i][k][0] = (1 << (k+1)) - gain[i][k][0];
}
}
}
for(int e = 1; e < lgN; e++)
{
for(int i = 0; i <= N; i++)
{
for(int k = 0; k < lgS; k++)
{
nxt[i][k][e] = nxt[ nxt[i][k][e-1] ][k][e-1];
gain[i][k][e] = gain[i][k][e-1] + gain[ nxt[i][k][e-1] ][k][e-1];
min_change[i][k][e] = min(min_change[i][k][e-1], min_change[ nxt[i][k][e-1] ][k][e-1] - gain[i][k][e-1]);
}
}
}
}
long long simulate(int x, int z)
{
int X = x;
long long Z = z;
for(int k = 0; k < lgS; k++)
{
cerr << "\n\n\n";
cerr << "k = " << k << '\n';
cerr << "X = " << X << '\n';
cerr << "Z = " << Z << '\n';
if((1 << (k+1)) <= Z) continue;
cerr << "entered!\n";
cerr << "Z = " << Z << '\n';
for(int e = lgN - 1; e >= 0; e--)
{
cerr << X << ' ' << k << ' ' << e << ' ' << min_change[X][k][e] << ' ' << nxt[X][k][e] << ' ' << gain[X][k][e] << '\n';
if(Z >= min_change[X][k][e]) continue;
Z += gain[X][k][e];
X = nxt[X][k][e];
if(X == N) return Z;
}
cerr << "Z = " << Z << '\n';
assert((1 << k) <= Z);
assert(Z < (1 << (k+1)));
if(Z >= S[X])
{
Z += S[X];
X = W[X];
}
else
{
Z += P[X];
X = L[X];
}
if(X == N) return Z;
cerr << "after manual operation, Z = " << Z << '\n';
}
return Z;
}