Submission #829431

#	Time	Username	Problem	Language	Result	Execution time	Memory
829431		ymm	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	1755 ms	1206220 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;

const int N = 50'010;
const int lg = 24;
const int S = 20;
int nxt[S][lg][N];
ll add[S][lg][N];
ll mn[S][lg][N];
ll mx[S][lg][N];
vector<int> s, p, w, l;
vector<int> cmp, scmp;
int n;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	::n = n;
	::s = s;
	::p = p;
	::w = w;
	::l = l;
	Loop (i,0,S-1)
		cmp.push_back(64<<i);
	Loop (i,0,n)
		scmp.push_back(lower_bound(cmp.begin(), cmp.end(), s[i]) - cmp.begin());
	Loop (k,0,cmp.size()+1) {
		Loop (i,0,n) {
			nxt[k][0][i] = (scmp[i] < k? w[i]: l[i]);
			add[k][0][i] = (scmp[i] < k? s[i]: p[i]);
			mn[k][0][i] = (scmp[i] < k? s[i]: 0);
			mx[k][0][i] = (scmp[i] < k? (ll)1e18: s[i]);
		}
		nxt[k][0][n] = n;
		Loop (j,0,lg-1) Loop (i,0,n+1) {
			nxt[k][j+1][i] = nxt[k][j][nxt[k][j][i]];
			add[k][j+1][i] = add[k][j][i] + add[k][j][nxt[k][j][i]];
			mn[k][j+1][i] = max(mn[k][j][i], mn[k][j][nxt[k][j][i]] - add[k][j][i]);
			mx[k][j+1][i] = min(mx[k][j][i], mx[k][j][nxt[k][j][i]] - add[k][j][i]);
		}
	}
}

long long simulate(int x, int z) {
	ll val = z;
	int k = 0;
	while (val < 64 && x != n) {
		if (val < s[x]) {
			val += p[x];
			x = l[x];
		} else {
			val += s[x];
			x = w[x];
		}
	}
	for (;;) {
		LoopR (i,0,lg) {
			if (mn[k][i][x] <= val && val < mx[k][i][x]) {
				val += add[k][i][x];
				x = nxt[k][i][x];
			}
		}
		if (x == n)
			break;
		assert(val >= s[x]);
		if (val < s[x]) {
			val += p[x];
			x = l[x];
		} else {
			val += s[x];
			x = w[x];
		}
		k = upper_bound(cmp.begin(), cmp.end(), val) - cmp.begin();
	}
	return val;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
dungeons.cpp:29:2: note: in expansion of macro 'Loop'
   29 |  Loop (k,0,cmp.size()+1) {
      |  ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 0 / 11