oj.uz

Submission #444293

# Submission time Handle Problem Language Result Execution time Memory
444293 2021-07-13T14:03:42 Z hhhhaura Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3074 ms 1691132 KB 
#include "dungeons.h"
#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define ll long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) cerr << "Line " << __LINE__ << ": ", kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() {cerr << endl;}
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...);}
#else
#define print(...) 0
#define vprint(...) 0
#endif
int N, K = 6, sz, lg;
ll cur; 
vector<ll> P;
vector<int> S, W;
vector<vector<int>> to[20];
vector<vector<ll>> ge[20], lim[20];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	N = n, sz = 0, lg = 20, cur = 1, S = s, W = w;
	while(cur < 1e7) sz ++, cur = cur * K;
	P.assign(sz + 2, 1), P[sz + 1] = INF;
	rep(i, 1, sz) P[i] = P[i - 1] * K; 
	rep(seg, 0, sz) {
		int L = P[seg];
		to[seg].assign(lg + 1, vector<int>(n + 1, n));
		ge[seg].assign(lg + 1, vector<ll>(n + 1, 0ll));
		lim[seg].assign(lg + 1, vector<ll>(n + 1, INF));
		rep(i, 0, n - 1) {
			if(s[i] < L) {
				to[seg][0][i] = w[i];
				ge[seg][0][i] = s[i];
				lim[seg][0][i] = INF;
			}
			else {
				to[seg][0][i] = l[i];
				ge[seg][0][i] = p[i];
				lim[seg][0][i] = s[i];
			}
		}
		rep(i, 1, lg) rep(j, 0, n) {
			to[seg][i][j] = to[seg][i - 1][to[seg][i - 1][j]];
			ge[seg][i][j] = ge[seg][i - 1][j] + ge[seg][i - 1][to[seg][i - 1][j]];
			lim[seg][i][j] = min(lim[seg][i - 1][j], 
				lim[seg][i - 1][to[seg][i - 1][j]] - ge[seg][i - 1][j]);
		}
	}
	return;
}
pair<int, ll> go(int id, int x, ll z) {
	rrep(i, 0, lg) {
		if(lim[id][i][x] > z) {
			z += ge[id][i][x];
			x = to[id][i][x];
		}
	}
	if(x == N) return {x, z};
	if(z >= S[x]) z += S[x], x = W[x];
	else z += ge[id][0][x], x = to[id][0][x];
	return {x, z};
} 
ll simulate(int x, int z) {
	ll cost = z;
	rep(i, 0, sz) {
		while(cost < P[i + 1]) {
			tie(x, cost) = go(i, x, cost);
			if(x == N) return cost;
		}
	}
	assert(x == N);
	return cost;
}

Compilation message

dungeons.cpp:5: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    5 | #pragma loop-opt(on)
      | 
dungeons.cpp:25:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
dungeons.cpp:25:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   25 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~

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 7 ms 8600 KB Output is correct
4 Correct 172 ms 210464 KB Output is correct
5 Correct 7 ms 8652 KB Output is correct
6 Correct 174 ms 210336 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 1351 ms 1686436 KB Output is correct
3 Correct 1348 ms 1686336 KB Output is correct
4 Correct 1347 ms 1687860 KB Output is correct
5 Correct 1432 ms 1687356 KB Output is correct
6 Correct 1489 ms 1685392 KB Output is correct
7 Correct 1389 ms 1682928 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 242 ms 210880 KB Output is correct
3 Correct 227 ms 210892 KB Output is correct
4 Correct 189 ms 210856 KB Output is correct
5 Correct 182 ms 210812 KB Output is correct
6 Correct 285 ms 210808 KB Output is correct
7 Correct 379 ms 210920 KB Output is correct
8 Correct 207 ms 210932 KB Output is correct
9 Correct 216 ms 210820 KB Output is correct
10 Correct 199 ms 210808 KB Output is correct
11 Correct 209 ms 210928 KB Output is correct
12 Correct 864 ms 210856 KB Output is correct
13 Correct 748 ms 210808 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 242 ms 210880 KB Output is correct
3 Correct 227 ms 210892 KB Output is correct
4 Correct 189 ms 210856 KB Output is correct
5 Correct 182 ms 210812 KB Output is correct
6 Correct 285 ms 210808 KB Output is correct
7 Correct 379 ms 210920 KB Output is correct
8 Correct 207 ms 210932 KB Output is correct
9 Correct 216 ms 210820 KB Output is correct
10 Correct 199 ms 210808 KB Output is correct
11 Correct 209 ms 210928 KB Output is correct
12 Correct 864 ms 210856 KB Output is correct
13 Correct 748 ms 210808 KB Output is correct
14 Correct 4 ms 4428 KB Output is correct
15 Correct 221 ms 210820 KB Output is correct
16 Correct 247 ms 210912 KB Output is correct
17 Correct 198 ms 211004 KB Output is correct
18 Correct 210 ms 210896 KB Output is correct
19 Correct 291 ms 210828 KB Output is correct
20 Correct 231 ms 210888 KB Output is correct
21 Correct 241 ms 210792 KB Output is correct
22 Correct 226 ms 210840 KB Output is correct
23 Correct 227 ms 210912 KB Output is correct
24 Correct 336 ms 210812 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 242 ms 210880 KB Output is correct
3 Correct 227 ms 210892 KB Output is correct
4 Correct 189 ms 210856 KB Output is correct
5 Correct 182 ms 210812 KB Output is correct
6 Correct 285 ms 210808 KB Output is correct
7 Correct 379 ms 210920 KB Output is correct
8 Correct 207 ms 210932 KB Output is correct
9 Correct 216 ms 210820 KB Output is correct
10 Correct 199 ms 210808 KB Output is correct
11 Correct 209 ms 210928 KB Output is correct
12 Correct 864 ms 210856 KB Output is correct
13 Correct 748 ms 210808 KB Output is correct
14 Correct 4 ms 4428 KB Output is correct
15 Correct 221 ms 210820 KB Output is correct
16 Correct 247 ms 210912 KB Output is correct
17 Correct 198 ms 211004 KB Output is correct
18 Correct 210 ms 210896 KB Output is correct
19 Correct 291 ms 210828 KB Output is correct
20 Correct 231 ms 210888 KB Output is correct
21 Correct 241 ms 210792 KB Output is correct
22 Correct 226 ms 210840 KB Output is correct
23 Correct 227 ms 210912 KB Output is correct
24 Correct 336 ms 210812 KB Output is correct
25 Correct 175 ms 210036 KB Output is correct
26 Correct 242 ms 210912 KB Output is correct
27 Correct 222 ms 210804 KB Output is correct
28 Correct 233 ms 210804 KB Output is correct
29 Correct 252 ms 210820 KB Output is correct
30 Correct 276 ms 210812 KB Output is correct
31 Correct 271 ms 210808 KB Output is correct
32 Correct 405 ms 210940 KB Output is correct
33 Correct 764 ms 210804 KB Output is correct
34 Correct 1389 ms 210784 KB Output is correct
35 Correct 671 ms 210808 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4428 KB Output is correct
2 Correct 1351 ms 1686436 KB Output is correct
3 Correct 1348 ms 1686336 KB Output is correct
4 Correct 1347 ms 1687860 KB Output is correct
5 Correct 1432 ms 1687356 KB Output is correct
6 Correct 1489 ms 1685392 KB Output is correct
7 Correct 1389 ms 1682928 KB Output is correct
8 Correct 5 ms 4428 KB Output is correct
9 Correct 242 ms 210880 KB Output is correct
10 Correct 227 ms 210892 KB Output is correct
11 Correct 189 ms 210856 KB Output is correct
12 Correct 182 ms 210812 KB Output is correct
13 Correct 285 ms 210808 KB Output is correct
14 Correct 379 ms 210920 KB Output is correct
15 Correct 207 ms 210932 KB Output is correct
16 Correct 216 ms 210820 KB Output is correct
17 Correct 199 ms 210808 KB Output is correct
18 Correct 209 ms 210928 KB Output is correct
19 Correct 864 ms 210856 KB Output is correct
20 Correct 748 ms 210808 KB Output is correct
21 Correct 4 ms 4428 KB Output is correct
22 Correct 221 ms 210820 KB Output is correct
23 Correct 247 ms 210912 KB Output is correct
24 Correct 198 ms 211004 KB Output is correct
25 Correct 210 ms 210896 KB Output is correct
26 Correct 291 ms 210828 KB Output is correct
27 Correct 231 ms 210888 KB Output is correct
28 Correct 241 ms 210792 KB Output is correct
29 Correct 226 ms 210840 KB Output is correct
30 Correct 227 ms 210912 KB Output is correct
31 Correct 336 ms 210812 KB Output is correct
32 Correct 175 ms 210036 KB Output is correct
33 Correct 242 ms 210912 KB Output is correct
34 Correct 222 ms 210804 KB Output is correct
35 Correct 233 ms 210804 KB Output is correct
36 Correct 252 ms 210820 KB Output is correct
37 Correct 276 ms 210812 KB Output is correct
38 Correct 271 ms 210808 KB Output is correct
39 Correct 405 ms 210940 KB Output is correct
40 Correct 764 ms 210804 KB Output is correct
41 Correct 1389 ms 210784 KB Output is correct
42 Correct 671 ms 210808 KB Output is correct
43 Correct 0 ms 300 KB Output is correct
44 Correct 4 ms 4532 KB Output is correct
45 Correct 1883 ms 1691132 KB Output is correct
46 Correct 1573 ms 1686508 KB Output is correct
47 Correct 1607 ms 1686988 KB Output is correct
48 Correct 1505 ms 1689060 KB Output is correct
49 Correct 1921 ms 1690988 KB Output is correct
50 Correct 1383 ms 1688608 KB Output is correct
51 Correct 1360 ms 1689152 KB Output is correct
52 Correct 1399 ms 1686876 KB Output is correct
53 Correct 2625 ms 1687544 KB Output is correct
54 Correct 2201 ms 1686684 KB Output is correct
55 Correct 2785 ms 1674256 KB Output is correct
56 Correct 2712 ms 1684624 KB Output is correct
57 Correct 2722 ms 1683636 KB Output is correct
58 Correct 2962 ms 1682768 KB Output is correct
59 Correct 3074 ms 1681552 KB Output is correct
60 Correct 2366 ms 1680732 KB Output is correct
61 Correct 2136 ms 1679440 KB Output is correct