oj.uz

Submission #1034843

# Submission time Handle Problem Language Result Execution time Memory
1034843 2024-07-25T19:46:29 Z Boas Dungeons Game (IOI21_dungeons) C++17
25 / 100
 983 ms 2097152 KB 
#include <bits/stdc++.h>
using namespace std;

#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define loop1(x, i) for (int i = 1; i <= x; i++)
#define ALL(x) begin(x), end(x)
#define pb push_back
#define int long long

typedef vector<int> vi;
typedef vector<signed> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#include "dungeons.h"

int N;
vvvi par, dif;
int sCnt = 0;
vi lvls;

void init(signed n, vi32 s, vi32 p, vi32 w, vi32 l)
{
	N = n;
	set<int> levels = {0};
	loop(n, i) levels.insert(s[i]);
	sCnt = levels.size();
	par = dif = vvvi(sCnt, vvi(30, vi(n + 1)));
	lvls = vi(ALL(levels));
	loop(sCnt, j)
	{
		loop(n, i)
		{
			if (s[i] > lvls[j])
			{
				par[j][0][i] = l[i];
				dif[j][0][i] = p[i];
			}
			else
			{
				par[j][0][i] = w[i];
				dif[j][0][i] = s[i];
			}
		}
		dif[j][0][n] = 0;
		par[j][0][n] = n;
	}
	loop(sCnt, j)
	{
		loop1(29, x)
		{
			loop(n + 1, i)
			{
				int half = par[j][x - 1][i];
				par[j][x][i] = par[j][x - 1][half];
				dif[j][x][i] = dif[j][x - 1][i] + dif[j][x - 1][half];
			}
		}
	}
	lvls.pb((int)4e18);
	return;
}

int simulate(signed a, signed b)
{
	int x = a, z = b;
	loop(sCnt, j)
	{
		int s = lvls[j + 1];
		if (z < s)
		{
			rev(30, i)
			{
				if (dif[j][i][x] + z < s && par[j][i][x] != N)
				{
					z += dif[j][i][x];
					x = par[j][i][x];
				}
			}
			z += dif[j][0][x];
			x = par[j][0][x];
			if (x == N)
				return z;
		}
	}
	return z;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 6 ms 11160 KB Output is correct
4 Runtime error 846 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 473168 KB Output is correct
2 Runtime error 983 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 81 ms 63556 KB Output is correct
3 Correct 84 ms 63540 KB Output is correct
4 Correct 78 ms 63060 KB Output is correct
5 Correct 73 ms 63060 KB Output is correct
6 Correct 92 ms 63312 KB Output is correct
7 Correct 89 ms 63324 KB Output is correct
8 Correct 74 ms 63048 KB Output is correct
9 Correct 87 ms 62944 KB Output is correct
10 Correct 71 ms 63196 KB Output is correct
11 Correct 82 ms 63112 KB Output is correct
12 Correct 127 ms 63312 KB Output is correct
13 Correct 134 ms 63316 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 81 ms 63556 KB Output is correct
3 Correct 84 ms 63540 KB Output is correct
4 Correct 78 ms 63060 KB Output is correct
5 Correct 73 ms 63060 KB Output is correct
6 Correct 92 ms 63312 KB Output is correct
7 Correct 89 ms 63324 KB Output is correct
8 Correct 74 ms 63048 KB Output is correct
9 Correct 87 ms 62944 KB Output is correct
10 Correct 71 ms 63196 KB Output is correct
11 Correct 82 ms 63112 KB Output is correct
12 Correct 127 ms 63312 KB Output is correct
13 Correct 134 ms 63316 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 110 ms 110408 KB Output is correct
16 Correct 136 ms 134308 KB Output is correct
17 Correct 129 ms 157264 KB Output is correct
18 Correct 187 ms 157472 KB Output is correct
19 Correct 175 ms 157572 KB Output is correct
20 Correct 134 ms 110164 KB Output is correct
21 Correct 171 ms 133856 KB Output is correct
22 Correct 103 ms 86676 KB Output is correct
23 Correct 142 ms 133844 KB Output is correct
24 Correct 211 ms 110416 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 81 ms 63556 KB Output is correct
3 Correct 84 ms 63540 KB Output is correct
4 Correct 78 ms 63060 KB Output is correct
5 Correct 73 ms 63060 KB Output is correct
6 Correct 92 ms 63312 KB Output is correct
7 Correct 89 ms 63324 KB Output is correct
8 Correct 74 ms 63048 KB Output is correct
9 Correct 87 ms 62944 KB Output is correct
10 Correct 71 ms 63196 KB Output is correct
11 Correct 82 ms 63112 KB Output is correct
12 Correct 127 ms 63312 KB Output is correct
13 Correct 134 ms 63316 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 110 ms 110408 KB Output is correct
16 Correct 136 ms 134308 KB Output is correct
17 Correct 129 ms 157264 KB Output is correct
18 Correct 187 ms 157472 KB Output is correct
19 Correct 175 ms 157572 KB Output is correct
20 Correct 134 ms 110164 KB Output is correct
21 Correct 171 ms 133856 KB Output is correct
22 Correct 103 ms 86676 KB Output is correct
23 Correct 142 ms 133844 KB Output is correct
24 Correct 211 ms 110416 KB Output is correct
25 Runtime error 868 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 473168 KB Output is correct
2 Runtime error 983 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -