| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1126929 | fgdsa | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define para pair<ll, ll>
const ll LOG = 24;
const ll LOG2 = 10;
const ll MAXN = 400000+1534;
const ll INF = 1e18+7;
struct Str{
int v;
ll sum;
ll mn;
};
Str jump[MAXN][LOG][LOG2];
int n;
vector<ll> s;
vector<ll> p;
vector<int> w;
vector<int> l;
Str operacjaLacznia(const Str a, const Str b){
Str res;
res.v = b.v;
res.sum = a.sum + b.sum;
res.mn = min(a.mn, b.mn - a.sum);
return res;
}
void gen(ll x, ll h){
for(int i = 0; i < n; ++i){
if(h < s[i]){
jump[i][0][x] = {l[i], p[i], s[i]};
}
else{
// if(i == n-1){
// jump[i][0][x] = {w[i], s[i], INF};
// }
jump[i][0][x] = {w[i], s[i], INF};
}
}
jump[n][0][x] = {n, 0, INF};
for(int i = 1; i < LOG; ++i){
for(int j = 0; j < n; ++j){
Str cur = jump[j][i-1][x];
cur = operacjaLacznia(cur, jump[cur.v][i-1][x]);
jump[j][i][x] = cur;
// if(x == 1 && i == 1 && j == 0){
// cerr << jump[j][i-1][x].v << " " << jump[j][i-1][x].sum << " " << jump[j][i-1][x].mn << "\n";
// cerr << jump[jump[j][i-1][x].v][i-1][x].mn << "\n";
// cerr << cur.v << " " << cur.sum << " " << cur.mn << "\n";
// }
}
}
return;
}
void init(int nT, vector<int> sT, vector<int> pT, vector<int> wT, vector<int> lT){
n = nT;
for(auto i : sT) s.push_back(i);
s.shrink_to_fit();
for(auto i : pT) p.push_back(i);
p.shrink_to_fit();
for(auto i : wT) w.push_back(i);
w.shrink_to_fit();
for(auto i : lT) l.push_back(i);
l.shrink_to_fit();
ll h = 1;
for(int i = 0; i < LOG2; ++i){
gen(i, h);
h *= 8;
}
return;
}
ll simulate(int x, int zT) {
ll z = zT;
ll cnt = 0;
ll pot8 = 1;
ll wyk = 0;
while(x != n){
while(pot8 * 8 <= z) pot8*=8, ++wyk;
for(int j = LOG-1; j >= 0; --j){
// cerr << j << ":\n";
// cerr << " " << x << " " << z << " " << pot2 << ": " << jump[x][j][wyk].v << " " << jump[x][j][wyk].mn << " " << jump[x][j][wyk].sum << '\n';
if(jump[x][j][wyk].mn > z){
z += jump[x][j][wyk].sum;
x = jump[x][j][wyk].v;
}
}
if(x == n) break;
z += s[x];
x = w[x];
// if(++cnt == 5){
// cerr << "\n";
// return 0;
// }
}
return z;
}