oj.uz

Submission #437450

# Submission time Handle Problem Language Result Execution time Memory
437450 2021-06-26T10:34:25 Z maomao90 Dungeons Game (IOI21_dungeons) C++17
25 / 100
 391 ms 373516 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#define REP(i, j, k) for (int i = j; i < k; i++)
#define RREP(i, j, k) for (int i = j; i >= k; i--)

template <class T>
inline void mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline void mxto(T& a, T b) {return a < b ? a = b, 1 : 0;}

typedef long long ll;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define ALL(x) x.begin(), x.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#ifdef DEBUG
#define debug(args...) _debug(args)
inline void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 1000000005
#define LINF 1000000000000000005
#define MAXN 100005
#define MAXL 30

int n;
vi s, p, w, l, v;
set<int> st;
int nxt[10][MAXL][MAXN];
ll d[10][MAXL][MAXN];

void init(int _n, vi _s, vi _p, vi _w, vi _l) {
	n = _n; s = _s, p = _p, w = _w, l = _l;
	s.pb(0);
	p.pb(0);
	w.pb(n);
	l.pb(n);
	REP (i, 0, n) {
		st.insert(s[i]);
	}
	v.pb(0);
	for (auto &i : st) {
		v.pb(i);
	}
	REP (it, 0, v.size()) {
		debug("%d:\n", v[it]);
		REP (i, 0, n + 1) {
			if (s[i] <= v[it]) {
			   	nxt[it][0][i] = w[i];
				d[it][0][i] = s[i];
				debug(" %d -> %d %d\n", i, w[i], s[i]);
			} else {
				nxt[it][0][i] = l[i];
				d[it][0][i] = p[i];
				debug(" %d -> %d %d\n", i, l[i], p[i]);
			}
		}
		REP (k, 1, MAXL) {
			REP (i, 0, n + 1) {
				nxt[it][k][i] = nxt[it][k - 1][nxt[it][k - 1][i]];
				d[it][k][i] = d[it][k - 1][i] + d[it][k - 1][nxt[it][k - 1][i]];
			}
		}
	}
	return;
}

ll simulate(int x, int z) {
	ll ans = z;
	REP (i, 0, v.size()) {
		ll mx = LINF;
		if (i + 1 != v.size()) mx = v[i + 1]; // < mx
		if (ans >= mx) continue;
		debug("%d\n", v[i]);
		RREP (k, MAXL - 1, 0) {
			if (ans + d[i][k][x] < mx) {
				ans += d[i][k][x];
				x = nxt[i][k][x];
				debug(" %d: %lld\n", x, ans);
			}
		}
		ans += d[i][0][x];
		x = nxt[i][0][x];
		debug(" %d: %lld\n", x, ans);
	}
	return ans;
}

Compilation message

dungeons.cpp: In function 'void init(int, vi, vi, vi, vi)':
dungeons.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define REP(i, j, k) for (int i = j; i < k; i++)
......
   61 |  REP (it, 0, v.size()) {
      |       ~~~~~~~~~~~~~~~                   
dungeons.cpp:61:2: note: in expansion of macro 'REP'
   61 |  REP (it, 0, v.size()) {
      |  ^~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:5:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define REP(i, j, k) for (int i = j; i < k; i++)
......
   86 |  REP (i, 0, v.size()) {
      |       ~~~~~~~~~~~~~~                    
dungeons.cpp:86:2: note: in expansion of macro 'REP'
   86 |  REP (i, 0, v.size()) {
      |  ^~~
dungeons.cpp:88:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   if (i + 1 != v.size()) mx = v[i + 1]; // < mx
      |       ~~~~~~^~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Runtime error 32 ms 6360 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 13656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 97 ms 39092 KB Output is correct
3 Correct 102 ms 39132 KB Output is correct
4 Correct 87 ms 39096 KB Output is correct
5 Correct 93 ms 39152 KB Output is correct
6 Correct 118 ms 39100 KB Output is correct
7 Correct 114 ms 39216 KB Output is correct
8 Correct 93 ms 39144 KB Output is correct
9 Correct 79 ms 39104 KB Output is correct
10 Correct 73 ms 39092 KB Output is correct
11 Correct 86 ms 39216 KB Output is correct
12 Correct 176 ms 39104 KB Output is correct
13 Correct 158 ms 39148 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 97 ms 39092 KB Output is correct
3 Correct 102 ms 39132 KB Output is correct
4 Correct 87 ms 39096 KB Output is correct
5 Correct 93 ms 39152 KB Output is correct
6 Correct 118 ms 39100 KB Output is correct
7 Correct 114 ms 39216 KB Output is correct
8 Correct 93 ms 39144 KB Output is correct
9 Correct 79 ms 39104 KB Output is correct
10 Correct 73 ms 39092 KB Output is correct
11 Correct 86 ms 39216 KB Output is correct
12 Correct 176 ms 39104 KB Output is correct
13 Correct 158 ms 39148 KB Output is correct
14 Correct 3 ms 3660 KB Output is correct
15 Correct 139 ms 74940 KB Output is correct
16 Correct 149 ms 92824 KB Output is correct
17 Correct 130 ms 110736 KB Output is correct
18 Correct 222 ms 110656 KB Output is correct
19 Correct 259 ms 110784 KB Output is correct
20 Correct 172 ms 75072 KB Output is correct
21 Correct 215 ms 92976 KB Output is correct
22 Correct 135 ms 57148 KB Output is correct
23 Correct 201 ms 92852 KB Output is correct
24 Correct 309 ms 74940 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1612 KB Output is correct
2 Correct 97 ms 39092 KB Output is correct
3 Correct 102 ms 39132 KB Output is correct
4 Correct 87 ms 39096 KB Output is correct
5 Correct 93 ms 39152 KB Output is correct
6 Correct 118 ms 39100 KB Output is correct
7 Correct 114 ms 39216 KB Output is correct
8 Correct 93 ms 39144 KB Output is correct
9 Correct 79 ms 39104 KB Output is correct
10 Correct 73 ms 39092 KB Output is correct
11 Correct 86 ms 39216 KB Output is correct
12 Correct 176 ms 39104 KB Output is correct
13 Correct 158 ms 39148 KB Output is correct
14 Correct 3 ms 3660 KB Output is correct
15 Correct 139 ms 74940 KB Output is correct
16 Correct 149 ms 92824 KB Output is correct
17 Correct 130 ms 110736 KB Output is correct
18 Correct 222 ms 110656 KB Output is correct
19 Correct 259 ms 110784 KB Output is correct
20 Correct 172 ms 75072 KB Output is correct
21 Correct 215 ms 92976 KB Output is correct
22 Correct 135 ms 57148 KB Output is correct
23 Correct 201 ms 92852 KB Output is correct
24 Correct 309 ms 74940 KB Output is correct
25 Runtime error 391 ms 373516 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 13656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -