Submission #437450

#	Time	Username	Problem	Language	Result	Execution time	Memory
437450		maomao90	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	391 ms	373516 KiB

dungeons

#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 (stderr)

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 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11