Submission #437691

#	Time	Username	Problem	Language	Result	Execution time	Memory
437691		gromperen	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	346 ms	253240 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

#define benutzen using
#define namensraum namespace
#define üblich std
#define ll long long

#define next nextcompile

benutzen namensraum üblich;

const int MAXN = 400005;
const int MAXM = 30;
const ll INF = 1e18+42069;

int next[10][MAXM][MAXN];
ll dp[10][MAXM][MAXN];
// int down[20][MAXN];

vector<int> v, s, p, w, l;
set<int> sv;

int n;

void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
	n = _n; s = _s; p = _p; w = _w; l = _l;


	// MAKE SO IT LOOPS INFINETELY AT N
	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);

	for (int i = 0; i < n; ++i) {
		sv.insert(s[i]);
	}

	v.push_back(0);
	for (auto &i : sv) {
		v.push_back(i);
	}


	for (int k = 0; k < v.size(); ++k) {
		//cout << v[k] << endl;
		for (int i = 0; i <= n; ++i) {
			if (s[i] <= v[k]) {
				next[k][0][i] = w[i];
				dp[k][0][i] = s[i];
			} else {
				next[k][0][i] = l[i];
				dp[k][0][i] = p[i];
			}
			//cout << i << " -> " << next[k][0][i] << " " << dp[k][0][i] << endl;
		}

		for (int q = 1; q < MAXM; ++q) {
			for (int i = 0; i <= n; ++i) {
				next[k][q][i] = next[k][q-1][ next[k][q-1][i] ];
				dp[k][q][i] = dp[k][q - 1][i] + dp[k][q - 1][ next[k][q - 1][i] ];
			}
		}

	}

	//cout <<"....." <<dp[0][2][n] << endl;


	return;
}

long long simulate(int x, int z) {
	ll ans = z;

	for (int i = 0; i < v.size() && x != n; ++i) {
		ll mx = INF;
		if (i < v.size() - 1) {
			mx = v[i + 1];
		}
		//cout << "V: "<< v[i] << endl;
		if (ans >= mx) {
			//cout << "MX: "<< mx << endl;
			continue;

		}
		for (int k = MAXM-1; k >= 0; --k) {
			if (ans + dp[i][k][x] < mx) {
				ans += dp[i][k][x];
				x = next[i][k][x];
				//cout << x << ": " <<ans << endl;
			}
		}
		ans += dp[i][0][x];
		x = next[i][0][x];
		//cout << x << ": " <<ans << endl;
	}
	return ans;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int k = 0; k < v.size(); ++k) {
      |                  ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |  for (int i = 0; i < v.size() && x != n; ++i) {
      |                  ~~^~~~~~~~~~
dungeons.cpp:79:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   if (i < v.size() - 1) {
      |       ~~^~~~~~~~~~~~~~

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