oj.uz

Submission #1049102

# Submission time Handle Problem Language Result Execution time Memory
1049102 2024-08-08T13:22:12 Z parsadox2 Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 539128 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 4e5 + 10 , Lg = 27;
const long long inf = 1e15 + 10;

int n;

vector <int> s , p , w , l;

long long f(long long x)
{
	if(x <= 0)
		return inf;
	return x;
}

struct item{
	long long mn;
	long long val;
	int id;
};

item a[2 * N][Lg];

item Get(item now , int len)
{
	if(len == 0)
		return now;
	long long id = now.id , mn = now.mn , val = now.val , dif = val - (val >= s[id]) * s[id];

	for(int i = Lg - 1 ; i >= 0 ; i--)  if((1 << i) <= len && a[id * 2 + (val >= s[id])][i].mn > dif)
	{
		item tmp = a[id * 2 + (val >= s[id])][i];
		return Get({min(mn , tmp.mn - dif) , tmp.val + dif , tmp.id} , len - (1 << i));
	}
	if(val >= s[id])
		return Get({min(mn , f(s[w[id]] - val - s[id])) , val + s[id] , w[id]} , len - 1);
	else
		return Get({min(mn , f(s[l[id]] - val - p[id])) , val + p[id] , l[id]} , len - 1);
}

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n = nn;
	s = ss;
	p = pp;
	w = ww;
	l = ll;
	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);
	for(int i = 0 ; i <= n ; i++)
	{
		a[i << 1][0] = {min(inf , f(s[l[i]] - p[i])) , p[i] , l[i]};
		a[(i << 1) + 1][0] = {f(s[w[i]] - 2 * s[i]) , 2 * s[i] , w[i]};
	}
	for(int j = 1 ; j < Lg ; j++)  for(int i = 0 ; i <= 2 * n + 1 ; i++)
	{
		a[i][j] = Get(a[i][j - 1] , (1 << (j - 1)));
	}
}

long long simulate(int x, int z) {
	item tmp = Get({inf , z , x} , 2e7);
	return tmp.val;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 90 ms 67512 KB Output is correct
5 Correct 4 ms 4700 KB Output is correct
6 Correct 111 ms 67480 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 5405 ms 537268 KB Output is correct
3 Correct 6242 ms 536800 KB Output is correct
4 Correct 5375 ms 537456 KB Output is correct
5 Correct 1077 ms 535344 KB Output is correct
6 Correct 5231 ms 535516 KB Output is correct
7 Correct 4038 ms 533804 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 99 ms 68404 KB Output is correct
3 Correct 134 ms 68404 KB Output is correct
4 Correct 113 ms 68484 KB Output is correct
5 Correct 151 ms 67976 KB Output is correct
6 Correct 147 ms 68524 KB Output is correct
7 Correct 148 ms 67992 KB Output is correct
8 Correct 134 ms 67904 KB Output is correct
9 Correct 124 ms 67980 KB Output is correct
10 Correct 135 ms 67652 KB Output is correct
11 Correct 137 ms 68236 KB Output is correct
12 Correct 357 ms 68240 KB Output is correct
13 Correct 247 ms 68036 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 99 ms 68404 KB Output is correct
3 Correct 134 ms 68404 KB Output is correct
4 Correct 113 ms 68484 KB Output is correct
5 Correct 151 ms 67976 KB Output is correct
6 Correct 147 ms 68524 KB Output is correct
7 Correct 148 ms 67992 KB Output is correct
8 Correct 134 ms 67904 KB Output is correct
9 Correct 124 ms 67980 KB Output is correct
10 Correct 135 ms 67652 KB Output is correct
11 Correct 137 ms 68236 KB Output is correct
12 Correct 357 ms 68240 KB Output is correct
13 Correct 247 ms 68036 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 197 ms 68228 KB Output is correct
16 Correct 142 ms 68160 KB Output is correct
17 Correct 138 ms 67992 KB Output is correct
18 Correct 180 ms 68148 KB Output is correct
19 Correct 173 ms 68164 KB Output is correct
20 Correct 371 ms 67912 KB Output is correct
21 Correct 264 ms 67916 KB Output is correct
22 Correct 236 ms 68120 KB Output is correct
23 Correct 152 ms 68040 KB Output is correct
24 Correct 336 ms 68392 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 99 ms 68404 KB Output is correct
3 Correct 134 ms 68404 KB Output is correct
4 Correct 113 ms 68484 KB Output is correct
5 Correct 151 ms 67976 KB Output is correct
6 Correct 147 ms 68524 KB Output is correct
7 Correct 148 ms 67992 KB Output is correct
8 Correct 134 ms 67904 KB Output is correct
9 Correct 124 ms 67980 KB Output is correct
10 Correct 135 ms 67652 KB Output is correct
11 Correct 137 ms 68236 KB Output is correct
12 Correct 357 ms 68240 KB Output is correct
13 Correct 247 ms 68036 KB Output is correct
14 Correct 2 ms 2648 KB Output is correct
15 Correct 197 ms 68228 KB Output is correct
16 Correct 142 ms 68160 KB Output is correct
17 Correct 138 ms 67992 KB Output is correct
18 Correct 180 ms 68148 KB Output is correct
19 Correct 173 ms 68164 KB Output is correct
20 Correct 371 ms 67912 KB Output is correct
21 Correct 264 ms 67916 KB Output is correct
22 Correct 236 ms 68120 KB Output is correct
23 Correct 152 ms 68040 KB Output is correct
24 Correct 336 ms 68392 KB Output is correct
25 Correct 119 ms 67396 KB Output is correct
26 Correct 111 ms 68400 KB Output is correct
27 Correct 330 ms 67916 KB Output is correct
28 Correct 279 ms 68036 KB Output is correct
29 Correct 135 ms 68264 KB Output is correct
30 Correct 479 ms 68220 KB Output is correct
31 Correct 675 ms 67912 KB Output is correct
32 Correct 733 ms 67908 KB Output is correct
33 Correct 275 ms 68040 KB Output is correct
34 Correct 273 ms 68016 KB Output is correct
35 Correct 467 ms 67916 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2652 KB Output is correct
2 Correct 5405 ms 537268 KB Output is correct
3 Correct 6242 ms 536800 KB Output is correct
4 Correct 5375 ms 537456 KB Output is correct
5 Correct 1077 ms 535344 KB Output is correct
6 Correct 5231 ms 535516 KB Output is correct
7 Correct 4038 ms 533804 KB Output is correct
8 Correct 2 ms 2648 KB Output is correct
9 Correct 99 ms 68404 KB Output is correct
10 Correct 134 ms 68404 KB Output is correct
11 Correct 113 ms 68484 KB Output is correct
12 Correct 151 ms 67976 KB Output is correct
13 Correct 147 ms 68524 KB Output is correct
14 Correct 148 ms 67992 KB Output is correct
15 Correct 134 ms 67904 KB Output is correct
16 Correct 124 ms 67980 KB Output is correct
17 Correct 135 ms 67652 KB Output is correct
18 Correct 137 ms 68236 KB Output is correct
19 Correct 357 ms 68240 KB Output is correct
20 Correct 247 ms 68036 KB Output is correct
21 Correct 2 ms 2648 KB Output is correct
22 Correct 197 ms 68228 KB Output is correct
23 Correct 142 ms 68160 KB Output is correct
24 Correct 138 ms 67992 KB Output is correct
25 Correct 180 ms 68148 KB Output is correct
26 Correct 173 ms 68164 KB Output is correct
27 Correct 371 ms 67912 KB Output is correct
28 Correct 264 ms 67916 KB Output is correct
29 Correct 236 ms 68120 KB Output is correct
30 Correct 152 ms 68040 KB Output is correct
31 Correct 336 ms 68392 KB Output is correct
32 Correct 119 ms 67396 KB Output is correct
33 Correct 111 ms 68400 KB Output is correct
34 Correct 330 ms 67916 KB Output is correct
35 Correct 279 ms 68036 KB Output is correct
36 Correct 135 ms 68264 KB Output is correct
37 Correct 479 ms 68220 KB Output is correct
38 Correct 675 ms 67912 KB Output is correct
39 Correct 733 ms 67908 KB Output is correct
40 Correct 275 ms 68040 KB Output is correct
41 Correct 273 ms 68016 KB Output is correct
42 Correct 467 ms 67916 KB Output is correct
43 Correct 1 ms 348 KB Output is correct
44 Correct 4 ms 1628 KB Output is correct
45 Correct 1206 ms 536240 KB Output is correct
46 Correct 3682 ms 533020 KB Output is correct
47 Correct 2733 ms 534200 KB Output is correct
48 Correct 4507 ms 539128 KB Output is correct
49 Correct 1200 ms 530132 KB Output is correct
50 Correct 5571 ms 529392 KB Output is correct
51 Correct 1308 ms 527268 KB Output is correct
52 Correct 6153 ms 528168 KB Output is correct
53 Execution timed out 7107 ms 527328 KB Time limit exceeded
54 Halted 0 ms 0 KB -