oj.uz

Submission #437691

# Submission time Handle Problem Language Result Execution time Memory
437691 2021-06-26T21:46:34 Z gromperen Dungeons Game (IOI21_dungeons) C++17
25 / 100
 346 ms 253240 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Runtime error 33 ms 5636 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 10584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 88 ms 39488 KB Output is correct
3 Correct 115 ms 39532 KB Output is correct
4 Correct 73 ms 39476 KB Output is correct
5 Correct 73 ms 39496 KB Output is correct
6 Correct 117 ms 39492 KB Output is correct
7 Correct 117 ms 39480 KB Output is correct
8 Correct 78 ms 39452 KB Output is correct
9 Correct 86 ms 39480 KB Output is correct
10 Correct 72 ms 39492 KB Output is correct
11 Correct 79 ms 39480 KB Output is correct
12 Correct 171 ms 39480 KB Output is correct
13 Correct 169 ms 39452 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 88 ms 39488 KB Output is correct
3 Correct 115 ms 39532 KB Output is correct
4 Correct 73 ms 39476 KB Output is correct
5 Correct 73 ms 39496 KB Output is correct
6 Correct 117 ms 39492 KB Output is correct
7 Correct 117 ms 39480 KB Output is correct
8 Correct 78 ms 39452 KB Output is correct
9 Correct 86 ms 39480 KB Output is correct
10 Correct 72 ms 39492 KB Output is correct
11 Correct 79 ms 39480 KB Output is correct
12 Correct 171 ms 39480 KB Output is correct
13 Correct 169 ms 39452 KB Output is correct
14 Correct 4 ms 4300 KB Output is correct
15 Correct 143 ms 75748 KB Output is correct
16 Correct 141 ms 93692 KB Output is correct
17 Correct 183 ms 111752 KB Output is correct
18 Correct 197 ms 111668 KB Output is correct
19 Correct 285 ms 111756 KB Output is correct
20 Correct 193 ms 75840 KB Output is correct
21 Correct 234 ms 93876 KB Output is correct
22 Correct 125 ms 57780 KB Output is correct
23 Correct 170 ms 93908 KB Output is correct
24 Correct 346 ms 76088 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1996 KB Output is correct
2 Correct 88 ms 39488 KB Output is correct
3 Correct 115 ms 39532 KB Output is correct
4 Correct 73 ms 39476 KB Output is correct
5 Correct 73 ms 39496 KB Output is correct
6 Correct 117 ms 39492 KB Output is correct
7 Correct 117 ms 39480 KB Output is correct
8 Correct 78 ms 39452 KB Output is correct
9 Correct 86 ms 39480 KB Output is correct
10 Correct 72 ms 39492 KB Output is correct
11 Correct 79 ms 39480 KB Output is correct
12 Correct 171 ms 39480 KB Output is correct
13 Correct 169 ms 39452 KB Output is correct
14 Correct 4 ms 4300 KB Output is correct
15 Correct 143 ms 75748 KB Output is correct
16 Correct 141 ms 93692 KB Output is correct
17 Correct 183 ms 111752 KB Output is correct
18 Correct 197 ms 111668 KB Output is correct
19 Correct 285 ms 111756 KB Output is correct
20 Correct 193 ms 75840 KB Output is correct
21 Correct 234 ms 93876 KB Output is correct
22 Correct 125 ms 57780 KB Output is correct
23 Correct 170 ms 93908 KB Output is correct
24 Correct 346 ms 76088 KB Output is correct
25 Runtime error 290 ms 253240 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 10584 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -