Submission #565635

#	Time	Username	Problem	Language	Result	Execution time	Memory
565635		PiejanVDC	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	67 ms	4820 KiB

dungeons

#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;

vector<int> S_;

struct S {
	vector<int>v = {-1,-1,-1,-1,-1};
	int nxt;
};

vector<vector<S>>win_jump;
vector<vector<int>>win_score;
vector<vector<S>>lose_jump;
vector<vector<int>>lose_score;

map<int,int>pos;

int n;

void init(int N, vector<int>s, vector<int>p, vector<int>w, vector<int>l) {
	n = N;
	set<int>st;
	
	for(auto z : s)
		st.insert(z);
	
	auto it = st.begin();
	for(int i = 0 ; i < min(5, (int)st.size()) ; i++, it++)
		S_.push_back(*it), pos[*it] = i;
	
	while((int)S_.size() < 5)
		S_.push_back(-1);

	win_jump.resize(n+5);
	win_score.resize(n+5);
	lose_jump.resize(n+5);
	lose_score.resize(n+5);

	for(int i = 0 ; i <= n ; i++)
		win_jump[i].resize(32), win_score[i].resize(32), lose_jump[i].resize(32), lose_score[i].resize(32);

	w.push_back(n), l.push_back(n);

	for(int i = 0 ; i <= n ; i++) {
		win_jump[i][0].v[pos[s[i]]] = s[i];
		win_jump[i][0].nxt = w[i];
		win_score[i][0] = s[i];
		lose_jump[i][0].v[pos[s[i]]] = s[i];
		lose_jump[i][0].nxt = l[i];
		lose_score[i][0] = p[i];
	}

	for(int j = 1 ; j <= 30 ; j++) {
		for(int i = 0 ; i <= n ; i++) {
			
			win_score[i][j] = win_score[i][j-1] + win_score[win_jump[i][j-1].nxt][j-1];
			lose_score[i][j] = lose_score[i][j-1] + lose_score[lose_jump[i][j-1].nxt][j-1];
			win_jump[i][j].nxt = win_jump[win_jump[i][j-1].nxt][j-1].nxt;
			lose_jump[i][j].nxt = lose_jump[lose_jump[i][j-1].nxt][j-1].nxt;
			
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(win_jump[win_jump[i][j-1].nxt][j-1].v[ii] != -1) {
					win_jump[i][j].v[ii] = win_jump[win_jump[i][j-1].nxt][j-1].v[ii] - win_score[i][j-1];
				} else if(win_jump[i][j-1].v[ii] != -1) {
					win_jump[i][j].v[ii] = win_jump[i][j-1].v[ii];
				}
				if(lose_jump[lose_jump[i][j-1].nxt][j-1].v[ii] != -1) {
					lose_jump[i][j].v[ii] = lose_jump[lose_jump[i][j-1].nxt][j-1].v[ii] - lose_score[i][j-1];
				} else if(lose_jump[i][j-1].v[ii] != -1) {
					lose_jump[i][j].v[ii] = lose_jump[i][j-1].v[ii];
				}
				//cout << i << " " << j << " " << ii << " " << win_jump[i][j].v[ii] << " " << lose_jump[i][j].v[ii] << "\n";
			}
		}
	}
}

long long simulate(int x, int z) {
	long long s = z;
	while(x != n) {
		
		for(int j = 30 ; j >= 0 ; j--) {
			bool ok = lose_jump[x][j].nxt != n;
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(lose_jump[x][j].v[ii]-s <= 0)
					ok = 0;
			}
			if(ok)
				s += lose_score[x][j], x = lose_jump[x][j].nxt;
		}
		
		cout << x << " ";

		for(int j = 30 ; j >= 0 ; j--) {
			bool ok = win_jump[x][j].nxt != n;
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(win_jump[x][j].v[ii]-s > 0)
					ok = 0;
			}
			if(ok)
				s += win_score[x][j], x = win_jump[x][j].nxt;
		}
		
		cout << x << " ";

		if(x != n) {
			bool ok = 1;
			for(int ii = 0 ; ii < 5 ; ii++) {
				if(win_jump[x][0].v[ii]-s > 0)
					ok = 0;
			}
			if(ok)
				s += win_score[x][0], x = win_jump[x][0].nxt;
			else
				s += lose_score[x][0], x = lose_jump[x][0].nxt;
		}

	}

	assert(x == n);
	return s;
}

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