Submission #784874

#	Time	Username	Problem	Language	Result	Execution time	Memory
784874		caganyanmaz	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	8 ms	5204 KiB

dungeons

#include "dungeons.h"
#define pb push_back
#include <vector>
#include <bits/stdc++.h>
using namespace std;

//#define DEBUGGING

void __print(int i) { cerr << i; }
void __print(const char* c) { cerr << c; }
void __print(long long i) { cerr << i; }

template<typename T>
void __print(T& t) { int f = 0; cerr << "{"; for (auto& i : t) { cerr << (f++ ? ", " : ""); __print(i); } cerr << "}"; }
void _print() { cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); }

#ifdef DEBUGGING
#define debug(x...) cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...) 42
#endif

constexpr static int MXSIZE = 4e5 + 1; 
constexpr static int MXLOG = 25;
constexpr static int MXMIN = 10;
constexpr static int MXLOGSIZE = MXLOG - MXMIN;

int bl[MXLOGSIZE][MXSIZE][MXLOG];
int blc[MXLOGSIZE][MXSIZE][MXLOG];
int blm[MXLOGSIZE][MXSIZE][MXLOG];
vector<int> s, p, w, l;
int n;

long long last[MXSIZE];

int safe_add(int a, int b);
int safe_remove(int a, int b);
void advance(int& x, long long& z);

void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll)
{
	ss.pb(0); pp.pb(0); ww.pb(n); ll.pb(n);
	s = ss; p = pp; w = ww; l = ll; n = nn;
	for (int i = 0; i < MXLOGSIZE; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (s[j] <= (1<<(i+MXMIN)))
			{
				bl[i][j][0] = w[j];
				blc[i][j][0] = s[j];
				blm[i][j][0] = s[j];
			}
			else
			{
				bl[i][j][0] = l[j];
				blc[i][j][0] = p[j];
				blm[i][j][0] = INT_MAX;
			}
		}
		bl[i][n][0] = n;
		blc[i][n][0] = 0;
		blm[i][n][0] = 0;
		for (int j = 1; j < MXLOG; j++)
		{
			for (int k = 0; k <= n; k++)
			{
				int prev = bl[i][k][j-1];
				bl[i][k][j] = bl[i][prev][j-1];
				blc[i][k][j] = safe_add(blc[i][k][j-1], blc[i][prev][j-1]);
				blm[i][k][j] = min(blm[i][k][j-1], safe_remove(blm[i][k-1][j], blc[i][k][j-1]));
			}
		}
	}
	for (int i = n-1; i >= 0; i--)
		last[i] = s[i] + last[w[i]];
}

long long simulate(int x, int zz)
{
	long long z = zz;
	while (z < (1 << MXMIN)&& x != n) 
	{
		debug(x, z);
		advance(x, z);
	}
	if (x == n)
		return z;
	for (int i = 0; i < MXLOGSIZE; i++)
	{
		for (int j = MXLOG-1; j >= 0; j--)
		{
			if (blm[i][x][j] < x)
			{
				z += blc[i][x][j];
				x = bl[i][x][j];
			}
		}
		advance(x, z);
	}
	z += last[x];
	return z;
}

int safe_add(int a, int b)
{
	if (INT_MAX - a < b)
		return INT_MAX;
	return a + b;
}

int safe_remove(int a, int b)
{
	if (b > a)
		return 0;
	return a - b;
}

void advance(int& x, long long& z)
{
	if (z >= s[x])
	{
		z += s[x];
		x = w[x];
	}
	else
	{
		z += p[x];
		x = l[x];
	}
}

Compilation message (stderr)

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:86:3: note: in expansion of macro 'debug'
   86 |   debug(x, z);
      |   ^~~~~

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