| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 609347 | FatihSolak | 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>
#define N 400005
#define K 40
#define X 10
using namespace std;
struct node{
int to;
long long val;
};
node sp[N][X][K];
vector<int> numbers;
int sz;
int n;
void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
n = n_;
for(int i = 0;i<n;i++){
numbers.push_back(s[i]);
}
sort(numbers.begin(),numbers.end());
numbers.resize(unique(numbers.begin(),numbers.end())-numbers.begin());
sz = numbers.size();
for(int x = 0;x<=sz;x++){
sp[n][x][0].to = n;
sp[n][x][0].val = 0;
for(int i = 0;i<n;i++){
int num = upper_bound(numbers.begin(),numbers.end(),s[i]) - numbers.begin();
if(num <= x){
sp[i][x][0].to = w[i];
sp[i][x][0].val = s[i];
}
else{
sp[i][x][0].to = l[i];
sp[i][x][0].val = p[i];
}
}
for(int j = 1;j<K;j++){
for(int i = 0;i<=n;i++){
sp[i][x][j].val = sp[i][x][j-1].val + sp[sp[i][x][j-1].to][x][j-1].val;
sp[i][x][j].to = sp[sp[i][x][j-1].to][x][j-1].to;
}
}
}
return;
}
long long simulate(int x, int z) {
long long pw = z;
int now = upper_bound(numbers.begin(),numbers.end(),pw) - numbers.begin();
while(x != n){
//cout << now << " " << x << " " << pw << endl;
if(now == sz){
for(int i = K-1;i>=0;i--){
if(sp[x][now][i].to != n){
pw += sp[x][now][i].val;
x = sp[x][now][i].to;
}
}
pw += sp[x][now][0].val;
x = sp[x][now][0].to;
assert(x == n);
}
else{
for(int i = K-1;i>=0;i--){
if(sp[x][now][i].val + pw < numbers[now]){
pw += sp[x][now][i].val;
x = sp[x][now][i].to;
}
}
pw += sp[x][now][0].val;
x = sp[x][now][0].to;
now++;
}
}
return pw;
}