| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 453612 | flappybird | 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>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAXS 40 //MAX sparse table
#define MAXI 9 //MAX interval
#define INF 1010101010
#define MAX 404040
#define B 3
vector<pll> win, lose; //next
int nxt[MAXI][MAXS][MAX], limit[MAXI][MAXS][MAX];
ll delta[MAXI][MAXS][MAX];
ll dp[MAX];
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
ll i;
win.resize(N + 1);
lose.resize(N + 1);
for (i = 0; i < N; i++) {
win[i] = { w[i], s[i] };
lose[i] = { l[i], p[i] };
}
ll k;
for (k = 0; k < MAXI; k++) {
ll low, high;
low = 1 << (B * k);
high = 1 << (B * (k + 1));
for (i = 0; i < N; i++) {
if (s[i] < low) {
nxt[k][0][i] = win[i].first;
delta[k][0][i] = win[i].second;
limit[k][0][i] = INF;
}
else if (s[i] >= high) {
nxt[k][0][i] = lose[i].first;
delta[k][0][i] = lose[i].second;
limit[k][0][i] = s[i];
}
else {
nxt[k][0][i] = lose[i].first;
delta[k][0][i] = lose[i].second;
limit[k][0][i] = s[i];
}
}
nxt[k][0][N] = N;
delta[k][0][N] = 0;
limit[k][0][N] = INF;
ll j;
for (j = 1; j < k + 1; j++) {
for (i = 0; i <= N; i++) {
ll v = nxt[k][j - 1][i];
nxt[k][j][i] = nxt[k][j - 1][v];
delta[k][j][i] = delta[k][j - 1][i] + delta[k][j - 1][v];
limit[k][j][i] = (int)max(0LL, min((ll)limit[k][j - 1][v] - delta[k][j - 1][i], (ll)limit[k][j - 1][i]));
}
}
}
return;
}
ll get(ll x) {
if (dp[x]) return dp[x];
if (x == N) return 0;
return dp[x] = (win[x].second + get(win[x].first));
}
long long simulate(int x, int Z) {
ll z = Z;
ll i;
for (i = 0; i < MAXI; i++) {
ll low, high;
high = 1 << (B * (i + 1));
if (i == MAXI - 1) return z + get(x);
if (high <= z) continue;
ll k;
ll c = 1;
while (c) {
c = 0;
if (high <= z) break;
for (k = 3 * i + 2; k >= 0; k--) {
if (limit[i][k][x] > z) {
c = 1;
z += delta[i][k][x];
x = nxt[i][k][x];
}
if (high <= z) break;
if (x == N) return z;
}
if (high <= z) break;
if (c == 0) {
if (z >= win[x].second) z += win[x].second, x = win[x].first;
else z += lose[x].second, x = lose[x].first;
if (x == N) return z;
if (high <= z) break;
c = 1;
}
if (x == N) return z;
if (high <= z) break;
}
}
}