oj.uz

Submission #463957

# Submission time Handle Problem Language Result Execution time Memory
463957 2021-08-12T05:22:20 Z flappybird Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1682012 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

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

#define MAXS 40 //MAX sparse table
#define MAXI 25 //MAX interval
#define MAXSI 351
#define INF 10101010
#define MAX 404040
#define B 1
#define max(x, y) ((x)>(y)?(x):(y))
#define min(x, y) ((x)<(y)?(x):(y))

vector<pair<int, int>> win, lose; //next
int nxt[MAX][MAXSI], limit[MAX][MAXSI], delta[MAX][MAXSI];
ll dp[MAX];
int f[30][30];
int N;

ll get(int 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;
	int i, j;
	for (i = 0; i <= 25; i++) {
		for (j = 0; j <= i; j++) f[i][j] = j + (i * (i + 1) / 2);
	}
	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] };
	}
	int k;
	for (k = 0; k < MAXI; k++) {
		int low, high;
		low = 1 << k;
		high = 1 << (k + 1);
		for (i = 0; i < N; i++) {
			if (s[i] < low) {
				nxt[i][f[k][0]] = win[i].first;
				delta[i][f[k][0]] = win[i].second;
				limit[i][f[k][0]] = INF;
			}
			else if (s[i] >= high) {
				nxt[i][f[k][0]] = lose[i].first;
				delta[i][f[k][0]] = lose[i].second;
				limit[i][f[k][0]] = s[i];
			}
			else {
				nxt[i][f[k][0]] = lose[i].first;
				delta[i][f[k][0]] = lose[i].second;
				limit[i][f[k][0]] = s[i];
			}
		}
		nxt[N][f[k][0]] = N;
		delta[N][f[k][0]] = 0;
		limit[N][f[k][0]] = INF;
		int j;
		for (j = 1; j <= k; ++j) {
			for (i = 0; i <= N; ++i) {
				int v = nxt[i][f[k][j - 1]];
				nxt[i][f[k][j]] = nxt[v][f[k][j - 1]];
				delta[i][f[k][j]] = min(50000000, delta[i][f[k][j - 1]] + delta[v][f[k][j - 1]]);
				limit[i][f[k][j]] = max(0, min(limit[v][f[k][j - 1]] - delta[i][f[k][j - 1]], limit[i][f[k][j - 1]]));
			}
		}
	}
	for (i = 0; i < N; i++) get(i);
	return;
}

long long simulate(int x, int Z) {
	ll z = Z;
	ll i;
	for (i = 0; i < MAXI; i++) {
		ll high;
		high = 1 << (i + 1);
		if (i == MAXI - 1) break;
		if (high <= z) continue;
		int k;
		bool c = 0;
		for (k = i; k >= 0; k--) {
			while (limit[x][f[i][k]] > z) {
				if (delta[x][f[i][k]] > 20000000) {
					c = 1;
					break;
				}
				z += delta[x][f[i][k]];
				x = nxt[x][f[i][k]];
				if (high <= z) break;
				if (x == N) return z;
			}
			if (c) break;
			if (high <= z) break;
			if (x == N) return z;
		}
		if (x == N) return z;
		if (c) {
			for (; k >= 0; k--) {
				if (limit[x][f[i][k]] > z) {
					while (delta[x][f[i][k]] <= 20000000) {
						z += delta[x][f[i][k]];
						x = nxt[x][f[i][k]];
						if (z > 1000000) return z + dp[x];
						if (high <= z) break;
						if (x == N) return z;
					}
					if (high <= z) break;
					if (x == N) return z;
				}
			}
			if (z > 1000000) return z + dp[x];
			continue;
		}
		if (high <= z) continue;
		if (z >= win[x].second) z += win[x].second, x = win[x].first;
		else z += lose[x].second, x = lose[x].first;
		if (x == N) break;
	}
	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 17 ms 8672 KB Output is correct
4 Correct 710 ms 209136 KB Output is correct
5 Correct 14 ms 8652 KB Output is correct
6 Correct 693 ms 209132 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 6301 ms 1678436 KB Output is correct
3 Correct 5866 ms 1681976 KB Output is correct
4 Correct 6213 ms 1682012 KB Output is correct
5 Correct 6688 ms 1671512 KB Output is correct
6 Correct 6501 ms 1678448 KB Output is correct
7 Correct 6149 ms 1681928 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4552 KB Output is correct
2 Correct 828 ms 209920 KB Output is correct
3 Correct 745 ms 210692 KB Output is correct
4 Correct 712 ms 211200 KB Output is correct
5 Correct 718 ms 210688 KB Output is correct
6 Correct 811 ms 209920 KB Output is correct
7 Correct 804 ms 209912 KB Output is correct
8 Correct 685 ms 211196 KB Output is correct
9 Correct 705 ms 209916 KB Output is correct
10 Correct 696 ms 211196 KB Output is correct
11 Correct 934 ms 209912 KB Output is correct
12 Correct 1205 ms 209920 KB Output is correct
13 Correct 914 ms 209920 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4552 KB Output is correct
2 Correct 828 ms 209920 KB Output is correct
3 Correct 745 ms 210692 KB Output is correct
4 Correct 712 ms 211200 KB Output is correct
5 Correct 718 ms 210688 KB Output is correct
6 Correct 811 ms 209920 KB Output is correct
7 Correct 804 ms 209912 KB Output is correct
8 Correct 685 ms 211196 KB Output is correct
9 Correct 705 ms 209916 KB Output is correct
10 Correct 696 ms 211196 KB Output is correct
11 Correct 934 ms 209912 KB Output is correct
12 Correct 1205 ms 209920 KB Output is correct
13 Correct 914 ms 209920 KB Output is correct
14 Correct 6 ms 4428 KB Output is correct
15 Correct 737 ms 209916 KB Output is correct
16 Correct 798 ms 209912 KB Output is correct
17 Correct 798 ms 210556 KB Output is correct
18 Correct 769 ms 210552 KB Output is correct
19 Correct 810 ms 209924 KB Output is correct
20 Correct 772 ms 210680 KB Output is correct
21 Correct 776 ms 210688 KB Output is correct
22 Correct 830 ms 210180 KB Output is correct
23 Correct 967 ms 209920 KB Output is correct
24 Correct 1048 ms 209916 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4552 KB Output is correct
2 Correct 828 ms 209920 KB Output is correct
3 Correct 745 ms 210692 KB Output is correct
4 Correct 712 ms 211200 KB Output is correct
5 Correct 718 ms 210688 KB Output is correct
6 Correct 811 ms 209920 KB Output is correct
7 Correct 804 ms 209912 KB Output is correct
8 Correct 685 ms 211196 KB Output is correct
9 Correct 705 ms 209916 KB Output is correct
10 Correct 696 ms 211196 KB Output is correct
11 Correct 934 ms 209912 KB Output is correct
12 Correct 1205 ms 209920 KB Output is correct
13 Correct 914 ms 209920 KB Output is correct
14 Correct 6 ms 4428 KB Output is correct
15 Correct 737 ms 209916 KB Output is correct
16 Correct 798 ms 209912 KB Output is correct
17 Correct 798 ms 210556 KB Output is correct
18 Correct 769 ms 210552 KB Output is correct
19 Correct 810 ms 209924 KB Output is correct
20 Correct 772 ms 210680 KB Output is correct
21 Correct 776 ms 210688 KB Output is correct
22 Correct 830 ms 210180 KB Output is correct
23 Correct 967 ms 209920 KB Output is correct
24 Correct 1048 ms 209916 KB Output is correct
25 Correct 750 ms 209144 KB Output is correct
26 Correct 813 ms 210012 KB Output is correct
27 Correct 726 ms 209920 KB Output is correct
28 Correct 717 ms 209912 KB Output is correct
29 Correct 858 ms 210004 KB Output is correct
30 Correct 795 ms 211156 KB Output is correct
31 Correct 749 ms 211204 KB Output is correct
32 Correct 966 ms 209924 KB Output is correct
33 Correct 977 ms 209860 KB Output is correct
34 Correct 1454 ms 209964 KB Output is correct
35 Correct 933 ms 210000 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 6301 ms 1678436 KB Output is correct
3 Correct 5866 ms 1681976 KB Output is correct
4 Correct 6213 ms 1682012 KB Output is correct
5 Correct 6688 ms 1671512 KB Output is correct
6 Correct 6501 ms 1678448 KB Output is correct
7 Correct 6149 ms 1681928 KB Output is correct
8 Correct 6 ms 4552 KB Output is correct
9 Correct 828 ms 209920 KB Output is correct
10 Correct 745 ms 210692 KB Output is correct
11 Correct 712 ms 211200 KB Output is correct
12 Correct 718 ms 210688 KB Output is correct
13 Correct 811 ms 209920 KB Output is correct
14 Correct 804 ms 209912 KB Output is correct
15 Correct 685 ms 211196 KB Output is correct
16 Correct 705 ms 209916 KB Output is correct
17 Correct 696 ms 211196 KB Output is correct
18 Correct 934 ms 209912 KB Output is correct
19 Correct 1205 ms 209920 KB Output is correct
20 Correct 914 ms 209920 KB Output is correct
21 Correct 6 ms 4428 KB Output is correct
22 Correct 737 ms 209916 KB Output is correct
23 Correct 798 ms 209912 KB Output is correct
24 Correct 798 ms 210556 KB Output is correct
25 Correct 769 ms 210552 KB Output is correct
26 Correct 810 ms 209924 KB Output is correct
27 Correct 772 ms 210680 KB Output is correct
28 Correct 776 ms 210688 KB Output is correct
29 Correct 830 ms 210180 KB Output is correct
30 Correct 967 ms 209920 KB Output is correct
31 Correct 1048 ms 209916 KB Output is correct
32 Correct 750 ms 209144 KB Output is correct
33 Correct 813 ms 210012 KB Output is correct
34 Correct 726 ms 209920 KB Output is correct
35 Correct 717 ms 209912 KB Output is correct
36 Correct 858 ms 210004 KB Output is correct
37 Correct 795 ms 211156 KB Output is correct
38 Correct 749 ms 211204 KB Output is correct
39 Correct 966 ms 209924 KB Output is correct
40 Correct 977 ms 209860 KB Output is correct
41 Correct 1454 ms 209964 KB Output is correct
42 Correct 933 ms 210000 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 5 ms 4428 KB Output is correct
45 Execution timed out 7172 ms 1668524 KB Time limit exceeded
46 Halted 0 ms 0 KB -