Submission #439117

#	Time	Username	Problem	Language	Result	Execution time	Memory
439117		Stickfish	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7063 ms	44492 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <cassert>
using namespace std;
using ll = long long;

const int MAXN = 4e5 + 123;
const int LOGVL = 26;
const ll INF = 1e9;

int n;
int edg[MAXN][2];
int p[MAXN][2];
pair<int, ll> cpredg0[LOGVL][MAXN];
pair<int, ll> cpredg1[LOGVL][MAXN];

int rpw2(int x){
	int lb = 0, ub = LOGVL;
	while(ub - lb > 1){
		int mb = (lb + ub) / 2;
		if((1 << mb) <= x){
			lb = mb;
		} else {
			ub = mb;
		}
	}
	return lb;
}

void get_next(ll& i, ll& vl){
	if(i >= n)
		return;
	if(vl >= p[i][0]){
		vl += p[i][0];
		i = edg[i][0];
	}  else {
		vl += p[i][1];
		i = edg[i][1];
	}
}

void init(int n0, vector<int> sv, vector<int> pv, vector<int> wv, vector<int> lv) {
	n = n0;
	for(int i = 0; i < n; ++i){
		edg[i][0] = wv[i];
		edg[i][1] = lv[i];
		p[i][0] = sv[i];
		p[i][1] = pv[i];
	}
	for(int lyr = 0; lyr < LOGVL; ++lyr){
		for(int i = 0; i < n; ++i){
			ll x = i, z = (1 << lyr);
			cpredg1[lyr][i] = cpredg0[lyr][i] = {x, 0};
			while(x < n && z >= p[x][0]){
				cpredg0[lyr][i] = {x, z - (1 << lyr)};
				get_next(x, z);
			}
			x = i, z = (1 << lyr);
			while(x < n && z < p[x][0]){
				cpredg1[lyr][i] = {x, z - (1 << lyr)};
				get_next(x, z);
			}
		}
	}
	//for(int lyr = 1; lyr < LOGVL; ++lyr){
		//for(int i = 0; i < n; ++i){
			//ll x = i, z = (1 << lyr);
			//while(x ==z >= p[x][0]){
				//cpredg0[lyr][i] = {x, z - (1 << lyr)};
				//if(x >= n)
					//break;
			//}
		//}
	//}
	return;
}

ll simulate(int x, int z){
	ll ans = z;
	ll i = x;
	while(i < n){
		ll lgans = rpw2(ans);
		
		ans += cpredg0[lgans][i].second;
		i = cpredg0[lgans][i].first;

		if(ans < 1e7){
			ans += cpredg1[lgans + 1][i].second;
			i = cpredg1[lgans + 1][i].first;
		}

		get_next(i, ans);
	}
	return ans;
}

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