Submission #443277

#	Time	Username	Problem	Language	Result	Execution time	Memory
443277		JvThunder	Dungeons Game (IOI21_dungeons)	C++17	24 / 100	4113 ms	2097152 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;
 
int N;
vector<int> S,P,W,L;
 
int base = 2;
const int nop = 63;
const int noa = 20;
const int sz = 50005;
 
ll jump[nop][noa][sz]; // 8^b,2^jump,pos
ll add[nop][noa][sz];
ll diff[nop][noa][sz];
ll mx[nop][noa][sz];
 
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	S = s; P = p; W = w; L = l; N = n;
	S.push_back(0);
	
	ll lim = 1;
	for(int bit=0;bit<nop;bit++)
	{
		for(int i=0;i<n;i++) 
		{
			if(s[i]<lim) add[bit][0][i] = s[i], jump[bit][0][i] = w[i];
			else add[bit][0][i] = p[i], jump[bit][0][i] = l[i];
			diff[bit][0][i] = add[bit][0][i]-s[i];
			mx[bit][0][i] = s[i];
		}
		add[bit][0][n] = 0, jump[bit][0][n] = n, diff[bit][0][n] = 0, mx[bit][0][n] = 0;
 
		for(int i=1;i<noa;i++)
		{
			for(int j=0;j<=n;j++)
			{
				ll nxt = jump[bit][i-1][j];
				add[bit][i][j] = add[bit][i-1][j] + add[bit][i-1][nxt];
				diff[bit][i][j] = max(diff[bit][i-1][j], add[bit][i-1][j]+diff[bit][i-1][nxt]);
				mx[bit][i][j] = max(mx[bit][i-1][j],mx[bit][i-1][nxt]);
				jump[bit][i][j] = jump[bit][i-1][nxt];
			}
		}
 
		lim *= base;
	}
	return;
}
 
ll simulate(int x, int z) 
{
	ll pos = x;
	ll str = z;
	
	ll lim = 1;
	ll phase = 0;
	while(pos!=N && phase<nop)
	{
		for(int i=noa-1;i>=0;i--)
		{
			//next stage
			if(str+diff[phase][i][pos]>=0 && mx[phase][i][pos]>=lim) continue;
			str += add[phase][i][pos];
			pos = jump[phase][i][pos];
		}
 
		if(pos==N) continue;
 
		if(str>=S[pos]) str += S[pos], pos = W[pos];
		else str += P[pos], pos = L[pos];
 
		phase++;
		lim *= base;
	}
 
	return str;
}

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