Submission #609351

#	Time	Username	Problem	Language	Result	Execution time	Memory
609351		FatihSolak	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	276 ms	237896 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define N 400005
#define K 30
#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){
			pw += sp[x][now][K-1].val;
			x = sp[x][now][K-1].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;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11