Submission #784895

#	Time	Username	Problem	Language	Result	Execution time	Memory
784895		caganyanmaz	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	6564 ms	1612728 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 MXLOG = 24;

#ifdef DEBUGGING
constexpr static int MXSIZE = 100;
constexpr static int MXMIN = 0;
#else
constexpr static int MXSIZE = 4e5 + 1; 
constexpr static int MXMIN = 10;
#endif
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(nn); ll.pb(nn);
	s = ss; p = pp; w = ww; l = ll; n = nn;
	debug(s, p, w, l);
	for (int i = 0; i < MXLOGSIZE; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			blm[i][j][0] = 1<<(i+MXMIN+1);
			if (s[j] <= (1<<(i+MXMIN)))
			{
				bl[i][j][0] = w[j];
				blc[i][j][0] = s[j];
			}
			else
			{
				bl[i][j][0] = l[j];
				blc[i][j][0] = p[j];
				blm[i][j][0] = min(blm[i][j][0], s[j]);
			}
		}
		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][prev][j-1], 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);
	}
	debug(x, z);
	if (x == n)
		return z;
	for (int i = 0; i < MXLOGSIZE; i++)
	{
		debug(i, x, z);
		for (int j = MXLOG-1; j >= 0; j--)
		{
			if (blm[i][x][j] > z)
			{
				z += blc[i][x][j];
				x = bl[i][x][j];
			}
		}
		debug(i, x, z);
		if (z < 1<<(i+MXMIN+1))
			advance(x, z);
		debug(i, x, z);
	}
	z += last[x];
	debug("-----------------");
	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 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:52:2: note: in expansion of macro 'debug'
   52 |  debug(s, p, w, l);
      |  ^~~~~
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:90:3: note: in expansion of macro 'debug'
   90 |   debug(x, z);
      |   ^~~~~
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:93:2: note: in expansion of macro 'debug'
   93 |  debug(x, z);
      |  ^~~~~
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:98:3: note: in expansion of macro 'debug'
   98 |   debug(i, x, z);
      |   ^~~~~
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:107:3: note: in expansion of macro 'debug'
  107 |   debug(i, x, z);
      |   ^~~~~
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:110:3: note: in expansion of macro 'debug'
  110 |   debug(i, x, z);
      |   ^~~~~
dungeons.cpp:22:21: warning: statement has no effect [-Wunused-value]
   22 | #define debug(x...) 42
      |                     ^~
dungeons.cpp:113:2: note: in expansion of macro 'debug'
  113 |  debug("-----------------");
      |  ^~~~~

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