oj.uz

Submission #465173

# Submission time Handle Problem Language Result Execution time Memory
465173 2021-08-15T09:45:07 Z flappybird Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1730688 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

#define MAXS 27 //MAX sparse table
#define MAXI 8 //MAX interval
#define B 3
#define INF 101010101010101010
#define MAX 400400

vector<pll> win, lose; //next
int nxt[MAX][MAXI][MAXS];
ll delta[MAX][MAXI][MAXS], limit[MAX][MAXI][MAXS];
int N;

ll dp[MAX];

ll get(ll x) {
	if (x == N) return 0;
	if (dp[x]) return dp[x];
	return dp[x] = get(win[x].first) + win[x].second;
}

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N = n;
	ll i;
	win.resize(N + 1);
	lose.resize(N + 1);
	for (i = 0; i < N; i++) {
		win[i] = { w[i], s[i] };
		lose[i] = { l[i], p[i] };
	}
	ll k;
	for (k = 0; k < MAXI; k++) {
		ll low, high;
		low = 1 << B * k;
		high = 1 << (B * (k + 1));
		for (i = 0; i < N; i++) {
			if (s[i] < low) {
				nxt[i][k][0] = win[i].first;
				delta[i][k][0] = win[i].second;
				limit[i][k][0] = INF;
			}
			else if (s[i] >= high) {
				nxt[i][k][0] = lose[i].first;
				delta[i][k][0] = lose[i].second;
				limit[i][k][0] = s[i];
			}
			else {
				nxt[i][k][0] = lose[i].first;
				delta[i][k][0] = lose[i].second;
				limit[i][k][0] = s[i];
			}
		}
		nxt[N][k][0] = N;
		delta[N][k][0] = 0;
		limit[N][k][0] = INF;
		ll j;
		for (j = 1; j < MAXS; j++) {
			for (i = 0; i <= N; i++) {
				ll v = nxt[i][k][j - 1];
				nxt[i][k][j] = nxt[v][k][j - 1];
				delta[i][k][j] = delta[i][k][j - 1] + delta[v][k][j - 1];
				limit[i][k][j] = max(0LL, min(limit[v][k][j - 1] - delta[i][k][j - 1], limit[i][k][j - 1]));
			}
		}
	}
	for (i = 0; i <= N; i++) get(i);
	return;
}

void move(int& x, ll& z) {
	if (z >= win[x].second) z += win[x].second, x = win[x].first;
	else z += lose[x].second, x = lose[x].first;
}

long long simulate(int x, int Z) {
	ll z = Z;
	ll i;
	for (i = 0; i < MAXI; i++) {
		if (x == N) break;
		if (z >= 10000000) break;
		ll high;
		high = 1 << (B * (i + 1));
		if (high <= z) continue;
		if (x == N) return z;
		if (z >= 10000000) return z + dp[x];
		ll k;
		while (z < high) {
			for (k = MAXS - 1; k >= 0; k--) {
				if (nxt[x][i][k] != N && limit[x][i][k] > z && delta[x][i][k] < 10000000) z += delta[x][i][k], x = nxt[x][i][k];
				if (z >= high) break;
			}
			if (x == N) return z;
			if (z >= high) break;
			if (x != N && z < high) move(x, z);
		}
	}
	return z + dp[x];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 10 ms 8916 KB Output is correct
4 Correct 564 ms 215256 KB Output is correct
5 Correct 13 ms 8912 KB Output is correct
6 Correct 592 ms 215296 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4556 KB Output is correct
2 Correct 5106 ms 1727008 KB Output is correct
3 Correct 5120 ms 1730464 KB Output is correct
4 Correct 4924 ms 1730688 KB Output is correct
5 Correct 4727 ms 1720228 KB Output is correct
6 Correct 4846 ms 1727140 KB Output is correct
7 Correct 4517 ms 1730656 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4556 KB Output is correct
2 Correct 642 ms 215952 KB Output is correct
3 Correct 583 ms 216800 KB Output is correct
4 Correct 551 ms 217340 KB Output is correct
5 Correct 564 ms 216808 KB Output is correct
6 Correct 630 ms 216068 KB Output is correct
7 Correct 613 ms 216040 KB Output is correct
8 Correct 598 ms 217332 KB Output is correct
9 Correct 555 ms 216164 KB Output is correct
10 Correct 567 ms 217316 KB Output is correct
11 Correct 718 ms 216152 KB Output is correct
12 Correct 858 ms 216040 KB Output is correct
13 Correct 666 ms 216160 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4556 KB Output is correct
2 Correct 642 ms 215952 KB Output is correct
3 Correct 583 ms 216800 KB Output is correct
4 Correct 551 ms 217340 KB Output is correct
5 Correct 564 ms 216808 KB Output is correct
6 Correct 630 ms 216068 KB Output is correct
7 Correct 613 ms 216040 KB Output is correct
8 Correct 598 ms 217332 KB Output is correct
9 Correct 555 ms 216164 KB Output is correct
10 Correct 567 ms 217316 KB Output is correct
11 Correct 718 ms 216152 KB Output is correct
12 Correct 858 ms 216040 KB Output is correct
13 Correct 666 ms 216160 KB Output is correct
14 Correct 5 ms 4556 KB Output is correct
15 Correct 584 ms 216044 KB Output is correct
16 Correct 612 ms 216152 KB Output is correct
17 Correct 579 ms 216636 KB Output is correct
18 Correct 553 ms 216680 KB Output is correct
19 Correct 636 ms 216036 KB Output is correct
20 Correct 611 ms 216864 KB Output is correct
21 Correct 605 ms 216812 KB Output is correct
22 Correct 654 ms 216296 KB Output is correct
23 Correct 748 ms 216044 KB Output is correct
24 Correct 895 ms 216036 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4556 KB Output is correct
2 Correct 642 ms 215952 KB Output is correct
3 Correct 583 ms 216800 KB Output is correct
4 Correct 551 ms 217340 KB Output is correct
5 Correct 564 ms 216808 KB Output is correct
6 Correct 630 ms 216068 KB Output is correct
7 Correct 613 ms 216040 KB Output is correct
8 Correct 598 ms 217332 KB Output is correct
9 Correct 555 ms 216164 KB Output is correct
10 Correct 567 ms 217316 KB Output is correct
11 Correct 718 ms 216152 KB Output is correct
12 Correct 858 ms 216040 KB Output is correct
13 Correct 666 ms 216160 KB Output is correct
14 Correct 5 ms 4556 KB Output is correct
15 Correct 584 ms 216044 KB Output is correct
16 Correct 612 ms 216152 KB Output is correct
17 Correct 579 ms 216636 KB Output is correct
18 Correct 553 ms 216680 KB Output is correct
19 Correct 636 ms 216036 KB Output is correct
20 Correct 611 ms 216864 KB Output is correct
21 Correct 605 ms 216812 KB Output is correct
22 Correct 654 ms 216296 KB Output is correct
23 Correct 748 ms 216044 KB Output is correct
24 Correct 895 ms 216036 KB Output is correct
25 Correct 606 ms 215264 KB Output is correct
26 Correct 627 ms 216004 KB Output is correct
27 Correct 555 ms 216036 KB Output is correct
28 Correct 570 ms 216040 KB Output is correct
29 Correct 607 ms 216036 KB Output is correct
30 Correct 628 ms 217320 KB Output is correct
31 Correct 618 ms 217324 KB Output is correct
32 Correct 848 ms 216164 KB Output is correct
33 Correct 949 ms 215956 KB Output is correct
34 Correct 1440 ms 216004 KB Output is correct
35 Correct 834 ms 216036 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4556 KB Output is correct
2 Correct 5106 ms 1727008 KB Output is correct
3 Correct 5120 ms 1730464 KB Output is correct
4 Correct 4924 ms 1730688 KB Output is correct
5 Correct 4727 ms 1720228 KB Output is correct
6 Correct 4846 ms 1727140 KB Output is correct
7 Correct 4517 ms 1730656 KB Output is correct
8 Correct 5 ms 4556 KB Output is correct
9 Correct 642 ms 215952 KB Output is correct
10 Correct 583 ms 216800 KB Output is correct
11 Correct 551 ms 217340 KB Output is correct
12 Correct 564 ms 216808 KB Output is correct
13 Correct 630 ms 216068 KB Output is correct
14 Correct 613 ms 216040 KB Output is correct
15 Correct 598 ms 217332 KB Output is correct
16 Correct 555 ms 216164 KB Output is correct
17 Correct 567 ms 217316 KB Output is correct
18 Correct 718 ms 216152 KB Output is correct
19 Correct 858 ms 216040 KB Output is correct
20 Correct 666 ms 216160 KB Output is correct
21 Correct 5 ms 4556 KB Output is correct
22 Correct 584 ms 216044 KB Output is correct
23 Correct 612 ms 216152 KB Output is correct
24 Correct 579 ms 216636 KB Output is correct
25 Correct 553 ms 216680 KB Output is correct
26 Correct 636 ms 216036 KB Output is correct
27 Correct 611 ms 216864 KB Output is correct
28 Correct 605 ms 216812 KB Output is correct
29 Correct 654 ms 216296 KB Output is correct
30 Correct 748 ms 216044 KB Output is correct
31 Correct 895 ms 216036 KB Output is correct
32 Correct 606 ms 215264 KB Output is correct
33 Correct 627 ms 216004 KB Output is correct
34 Correct 555 ms 216036 KB Output is correct
35 Correct 570 ms 216040 KB Output is correct
36 Correct 607 ms 216036 KB Output is correct
37 Correct 628 ms 217320 KB Output is correct
38 Correct 618 ms 217324 KB Output is correct
39 Correct 848 ms 216164 KB Output is correct
40 Correct 949 ms 215956 KB Output is correct
41 Correct 1440 ms 216004 KB Output is correct
42 Correct 834 ms 216036 KB Output is correct
43 Correct 0 ms 332 KB Output is correct
44 Correct 5 ms 4556 KB Output is correct
45 Correct 6356 ms 1720112 KB Output is correct
46 Correct 4682 ms 1720144 KB Output is correct
47 Correct 4733 ms 1720344 KB Output is correct
48 Correct 4661 ms 1726992 KB Output is correct
49 Correct 6545 ms 1720076 KB Output is correct
50 Correct 4938 ms 1726940 KB Output is correct
51 Correct 4550 ms 1725276 KB Output is correct
52 Correct 4848 ms 1726948 KB Output is correct
53 Execution timed out 7158 ms 1716956 KB Time limit exceeded
54 Halted 0 ms 0 KB -