oj.uz

Submission #1056065

# Submission time Handle Problem Language Result Execution time Memory
1056065 2024-08-13T07:34:10 Z fuad27 Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 1898652 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int N = 4e5+1;
const int lg = 25;
const int lgb = 12;
const int base = 4;
const long long inf = 2e9;
int up[lg][N][lgb];
int min_diff[lg][N][lgb];
long long sum[lg][N][lgb];
int n;
vector<int> s, p, w, l;
void init(int nn, std::vector<int> ss, std::vector<int> pp,
		std::vector<int> ww, std::vector<int> ll) {
	s=ss, p = pp, w = ww, l = ll;
	n = nn;
	for(int _ = 0;_<lg;_++) {
		for(int i = 0;i<=n;i++) {
			if(i == n) {
				up[_][i][0] = n;
				min_diff[_][i][0] = inf;
				sum[_][i][0] = 0;
			}
			else if(s[i] < (1ll<<_)) {
				up[_][i][0] = w[i];
				min_diff[_][i][0] = inf;
				sum[_][i][0] = s[i];
			}
			else {
				up[_][i][0] = l[i];
				min_diff[_][i][0] = s[i];
				sum[_][i][0] = p[i];
			}
		}
		for(int l = 1;l<lgb;l++) {
			for(int i = 0;i<=n;i++) {
				int at = i;
				long long sm = 0;
				long long mn_diff = inf;
				for(int k = 0;k<base;k++) {
					if(min_diff[_][at][l-1] != inf)
						mn_diff = max(0ll, min(mn_diff, min_diff[_][at][l-1]-sm));
					sm+=sum[_][at][l-1];
					at=up[_][at][l-1];
				}
				up[_][i][l] = at;
				min_diff[_][i][l] = mn_diff;
				sum[_][i][l] = sm;
			}
		}
	}
	return;
}
 
long long simulate(int x, int zz) {
	long long z = zz;
	int cnt=0;
	int idx=0;
	while(1) {
		if(x == n)break;
		cnt++;
		while((1ll<<idx) <= z) {
			idx++;
		}
		int ll = min(lg-1, idx-1);
		for(int j = lgb-1;j>=0;j--) {
			for(int _ = 1;_<base;_++) {
				if(up[ll][x][j] == n or (ll < lg-1 and min_diff[ll][x][j] <= z))continue;
				z += sum[ll][x][j];
				x = up[ll][x][j];
			}
		}
		if(s[x] <= z) {
			z+=s[x];
			x=w[x];
		}
		else if(s[x] > z) {
			z+=p[x];
			x=l[x];
		}
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25436 KB Output is correct
2 Correct 2 ms 27484 KB Output is correct
3 Correct 7 ms 33844 KB Output is correct
4 Correct 208 ms 247120 KB Output is correct
5 Correct 8 ms 33880 KB Output is correct
6 Correct 206 ms 247120 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 1934 ms 1898560 KB Output is correct
3 Correct 1894 ms 1898568 KB Output is correct
4 Correct 1931 ms 1898596 KB Output is correct
5 Correct 1857 ms 1898576 KB Output is correct
6 Correct 1860 ms 1898476 KB Output is correct
7 Correct 1739 ms 1898580 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 265 ms 249864 KB Output is correct
3 Correct 215 ms 248016 KB Output is correct
4 Correct 189 ms 247892 KB Output is correct
5 Correct 192 ms 247892 KB Output is correct
6 Correct 263 ms 247888 KB Output is correct
7 Correct 261 ms 247892 KB Output is correct
8 Correct 207 ms 247836 KB Output is correct
9 Correct 178 ms 248068 KB Output is correct
10 Correct 204 ms 247888 KB Output is correct
11 Correct 345 ms 247912 KB Output is correct
12 Correct 460 ms 247888 KB Output is correct
13 Correct 265 ms 248016 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 265 ms 249864 KB Output is correct
3 Correct 215 ms 248016 KB Output is correct
4 Correct 189 ms 247892 KB Output is correct
5 Correct 192 ms 247892 KB Output is correct
6 Correct 263 ms 247888 KB Output is correct
7 Correct 261 ms 247892 KB Output is correct
8 Correct 207 ms 247836 KB Output is correct
9 Correct 178 ms 248068 KB Output is correct
10 Correct 204 ms 247888 KB Output is correct
11 Correct 345 ms 247912 KB Output is correct
12 Correct 460 ms 247888 KB Output is correct
13 Correct 265 ms 248016 KB Output is correct
14 Correct 5 ms 29532 KB Output is correct
15 Correct 219 ms 248008 KB Output is correct
16 Correct 268 ms 248008 KB Output is correct
17 Correct 203 ms 247888 KB Output is correct
18 Correct 211 ms 247892 KB Output is correct
19 Correct 287 ms 247892 KB Output is correct
20 Correct 224 ms 247892 KB Output is correct
21 Correct 216 ms 247892 KB Output is correct
22 Correct 202 ms 247888 KB Output is correct
23 Correct 333 ms 247888 KB Output is correct
24 Correct 421 ms 248144 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29532 KB Output is correct
2 Correct 265 ms 249864 KB Output is correct
3 Correct 215 ms 248016 KB Output is correct
4 Correct 189 ms 247892 KB Output is correct
5 Correct 192 ms 247892 KB Output is correct
6 Correct 263 ms 247888 KB Output is correct
7 Correct 261 ms 247892 KB Output is correct
8 Correct 207 ms 247836 KB Output is correct
9 Correct 178 ms 248068 KB Output is correct
10 Correct 204 ms 247888 KB Output is correct
11 Correct 345 ms 247912 KB Output is correct
12 Correct 460 ms 247888 KB Output is correct
13 Correct 265 ms 248016 KB Output is correct
14 Correct 5 ms 29532 KB Output is correct
15 Correct 219 ms 248008 KB Output is correct
16 Correct 268 ms 248008 KB Output is correct
17 Correct 203 ms 247888 KB Output is correct
18 Correct 211 ms 247892 KB Output is correct
19 Correct 287 ms 247892 KB Output is correct
20 Correct 224 ms 247892 KB Output is correct
21 Correct 216 ms 247892 KB Output is correct
22 Correct 202 ms 247888 KB Output is correct
23 Correct 333 ms 247888 KB Output is correct
24 Correct 421 ms 248144 KB Output is correct
25 Correct 243 ms 247124 KB Output is correct
26 Correct 339 ms 248068 KB Output is correct
27 Correct 214 ms 247892 KB Output is correct
28 Correct 208 ms 247928 KB Output is correct
29 Correct 302 ms 248076 KB Output is correct
30 Correct 240 ms 248016 KB Output is correct
31 Correct 242 ms 247828 KB Output is correct
32 Correct 425 ms 247892 KB Output is correct
33 Correct 306 ms 247892 KB Output is correct
34 Correct 530 ms 247776 KB Output is correct
35 Correct 348 ms 247892 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29532 KB Output is correct
2 Correct 1934 ms 1898560 KB Output is correct
3 Correct 1894 ms 1898568 KB Output is correct
4 Correct 1931 ms 1898596 KB Output is correct
5 Correct 1857 ms 1898576 KB Output is correct
6 Correct 1860 ms 1898476 KB Output is correct
7 Correct 1739 ms 1898580 KB Output is correct
8 Correct 5 ms 29532 KB Output is correct
9 Correct 265 ms 249864 KB Output is correct
10 Correct 215 ms 248016 KB Output is correct
11 Correct 189 ms 247892 KB Output is correct
12 Correct 192 ms 247892 KB Output is correct
13 Correct 263 ms 247888 KB Output is correct
14 Correct 261 ms 247892 KB Output is correct
15 Correct 207 ms 247836 KB Output is correct
16 Correct 178 ms 248068 KB Output is correct
17 Correct 204 ms 247888 KB Output is correct
18 Correct 345 ms 247912 KB Output is correct
19 Correct 460 ms 247888 KB Output is correct
20 Correct 265 ms 248016 KB Output is correct
21 Correct 5 ms 29532 KB Output is correct
22 Correct 219 ms 248008 KB Output is correct
23 Correct 268 ms 248008 KB Output is correct
24 Correct 203 ms 247888 KB Output is correct
25 Correct 211 ms 247892 KB Output is correct
26 Correct 287 ms 247892 KB Output is correct
27 Correct 224 ms 247892 KB Output is correct
28 Correct 216 ms 247892 KB Output is correct
29 Correct 202 ms 247888 KB Output is correct
30 Correct 333 ms 247888 KB Output is correct
31 Correct 421 ms 248144 KB Output is correct
32 Correct 243 ms 247124 KB Output is correct
33 Correct 339 ms 248068 KB Output is correct
34 Correct 214 ms 247892 KB Output is correct
35 Correct 208 ms 247928 KB Output is correct
36 Correct 302 ms 248076 KB Output is correct
37 Correct 240 ms 248016 KB Output is correct
38 Correct 242 ms 247828 KB Output is correct
39 Correct 425 ms 247892 KB Output is correct
40 Correct 306 ms 247892 KB Output is correct
41 Correct 530 ms 247776 KB Output is correct
42 Correct 348 ms 247892 KB Output is correct
43 Correct 2 ms 25432 KB Output is correct
44 Correct 6 ms 31580 KB Output is correct
45 Correct 3379 ms 1898572 KB Output is correct
46 Correct 2080 ms 1898652 KB Output is correct
47 Correct 2111 ms 1898576 KB Output is correct
48 Correct 2021 ms 1898576 KB Output is correct
49 Correct 3717 ms 1898572 KB Output is correct
50 Correct 1956 ms 1898624 KB Output is correct
51 Correct 2013 ms 1898492 KB Output is correct
52 Correct 2172 ms 1898536 KB Output is correct
53 Execution timed out 7160 ms 1372524 KB Time limit exceeded
54 Halted 0 ms 0 KB -