oj.uz

Submission #784895

# Submission time Handle Problem Language Result Execution time Memory
784895 2023-07-16T17:34:34 Z caganyanmaz Dungeons Game (IOI21_dungeons) C++17
100 / 100
 6564 ms 1612728 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 7 ms 8660 KB Output is correct
4 Correct 270 ms 200580 KB Output is correct
5 Correct 7 ms 8660 KB Output is correct
6 Correct 250 ms 201484 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4564 KB Output is correct
2 Correct 3908 ms 1601120 KB Output is correct
3 Correct 3138 ms 1607996 KB Output is correct
4 Correct 3047 ms 1609508 KB Output is correct
5 Correct 2980 ms 1609512 KB Output is correct
6 Correct 4141 ms 1608024 KB Output is correct
7 Correct 3818 ms 1606216 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4692 KB Output is correct
2 Correct 462 ms 201356 KB Output is correct
3 Correct 406 ms 201340 KB Output is correct
4 Correct 454 ms 201404 KB Output is correct
5 Correct 416 ms 201432 KB Output is correct
6 Correct 520 ms 201428 KB Output is correct
7 Correct 541 ms 202696 KB Output is correct
8 Correct 428 ms 202416 KB Output is correct
9 Correct 335 ms 202364 KB Output is correct
10 Correct 446 ms 202256 KB Output is correct
11 Correct 968 ms 202668 KB Output is correct
12 Correct 1267 ms 202744 KB Output is correct
13 Correct 816 ms 202680 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4692 KB Output is correct
2 Correct 462 ms 201356 KB Output is correct
3 Correct 406 ms 201340 KB Output is correct
4 Correct 454 ms 201404 KB Output is correct
5 Correct 416 ms 201432 KB Output is correct
6 Correct 520 ms 201428 KB Output is correct
7 Correct 541 ms 202696 KB Output is correct
8 Correct 428 ms 202416 KB Output is correct
9 Correct 335 ms 202364 KB Output is correct
10 Correct 446 ms 202256 KB Output is correct
11 Correct 968 ms 202668 KB Output is correct
12 Correct 1267 ms 202744 KB Output is correct
13 Correct 816 ms 202680 KB Output is correct
14 Correct 4 ms 4692 KB Output is correct
15 Correct 376 ms 202808 KB Output is correct
16 Correct 476 ms 203096 KB Output is correct
17 Correct 518 ms 202544 KB Output is correct
18 Correct 548 ms 202612 KB Output is correct
19 Correct 507 ms 202648 KB Output is correct
20 Correct 614 ms 202372 KB Output is correct
21 Correct 692 ms 202480 KB Output is correct
22 Correct 776 ms 202544 KB Output is correct
23 Correct 1155 ms 202636 KB Output is correct
24 Correct 1620 ms 202708 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4692 KB Output is correct
2 Correct 462 ms 201356 KB Output is correct
3 Correct 406 ms 201340 KB Output is correct
4 Correct 454 ms 201404 KB Output is correct
5 Correct 416 ms 201432 KB Output is correct
6 Correct 520 ms 201428 KB Output is correct
7 Correct 541 ms 202696 KB Output is correct
8 Correct 428 ms 202416 KB Output is correct
9 Correct 335 ms 202364 KB Output is correct
10 Correct 446 ms 202256 KB Output is correct
11 Correct 968 ms 202668 KB Output is correct
12 Correct 1267 ms 202744 KB Output is correct
13 Correct 816 ms 202680 KB Output is correct
14 Correct 4 ms 4692 KB Output is correct
15 Correct 376 ms 202808 KB Output is correct
16 Correct 476 ms 203096 KB Output is correct
17 Correct 518 ms 202544 KB Output is correct
18 Correct 548 ms 202612 KB Output is correct
19 Correct 507 ms 202648 KB Output is correct
20 Correct 614 ms 202372 KB Output is correct
21 Correct 692 ms 202480 KB Output is correct
22 Correct 776 ms 202544 KB Output is correct
23 Correct 1155 ms 202636 KB Output is correct
24 Correct 1620 ms 202708 KB Output is correct
25 Correct 319 ms 201980 KB Output is correct
26 Correct 468 ms 203068 KB Output is correct
27 Correct 392 ms 202480 KB Output is correct
28 Correct 386 ms 202580 KB Output is correct
29 Correct 518 ms 202940 KB Output is correct
30 Correct 666 ms 202576 KB Output is correct
31 Correct 721 ms 202440 KB Output is correct
32 Correct 1039 ms 202556 KB Output is correct
33 Correct 417 ms 202616 KB Output is correct
34 Correct 986 ms 202404 KB Output is correct
35 Correct 687 ms 202528 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4564 KB Output is correct
2 Correct 3908 ms 1601120 KB Output is correct
3 Correct 3138 ms 1607996 KB Output is correct
4 Correct 3047 ms 1609508 KB Output is correct
5 Correct 2980 ms 1609512 KB Output is correct
6 Correct 4141 ms 1608024 KB Output is correct
7 Correct 3818 ms 1606216 KB Output is correct
8 Correct 4 ms 4692 KB Output is correct
9 Correct 462 ms 201356 KB Output is correct
10 Correct 406 ms 201340 KB Output is correct
11 Correct 454 ms 201404 KB Output is correct
12 Correct 416 ms 201432 KB Output is correct
13 Correct 520 ms 201428 KB Output is correct
14 Correct 541 ms 202696 KB Output is correct
15 Correct 428 ms 202416 KB Output is correct
16 Correct 335 ms 202364 KB Output is correct
17 Correct 446 ms 202256 KB Output is correct
18 Correct 968 ms 202668 KB Output is correct
19 Correct 1267 ms 202744 KB Output is correct
20 Correct 816 ms 202680 KB Output is correct
21 Correct 4 ms 4692 KB Output is correct
22 Correct 376 ms 202808 KB Output is correct
23 Correct 476 ms 203096 KB Output is correct
24 Correct 518 ms 202544 KB Output is correct
25 Correct 548 ms 202612 KB Output is correct
26 Correct 507 ms 202648 KB Output is correct
27 Correct 614 ms 202372 KB Output is correct
28 Correct 692 ms 202480 KB Output is correct
29 Correct 776 ms 202544 KB Output is correct
30 Correct 1155 ms 202636 KB Output is correct
31 Correct 1620 ms 202708 KB Output is correct
32 Correct 319 ms 201980 KB Output is correct
33 Correct 468 ms 203068 KB Output is correct
34 Correct 392 ms 202480 KB Output is correct
35 Correct 386 ms 202580 KB Output is correct
36 Correct 518 ms 202940 KB Output is correct
37 Correct 666 ms 202576 KB Output is correct
38 Correct 721 ms 202440 KB Output is correct
39 Correct 1039 ms 202556 KB Output is correct
40 Correct 417 ms 202616 KB Output is correct
41 Correct 986 ms 202404 KB Output is correct
42 Correct 687 ms 202528 KB Output is correct
43 Correct 1 ms 596 KB Output is correct
44 Correct 4 ms 4664 KB Output is correct
45 Correct 4440 ms 1612724 KB Output is correct
46 Correct 3104 ms 1608096 KB Output is correct
47 Correct 3030 ms 1608456 KB Output is correct
48 Correct 3056 ms 1610640 KB Output is correct
49 Correct 4731 ms 1612728 KB Output is correct
50 Correct 3865 ms 1610220 KB Output is correct
51 Correct 2936 ms 1610668 KB Output is correct
52 Correct 3943 ms 1608360 KB Output is correct
53 Correct 6514 ms 1609128 KB Output is correct
54 Correct 3609 ms 1610232 KB Output is correct
55 Correct 4509 ms 1609256 KB Output is correct
56 Correct 5177 ms 1609904 KB Output is correct
57 Correct 5342 ms 1610016 KB Output is correct
58 Correct 5471 ms 1610028 KB Output is correct
59 Correct 5207 ms 1610116 KB Output is correct
60 Correct 6564 ms 1609364 KB Output is correct
61 Correct 5778 ms 1609316 KB Output is correct