oj.uz

Submission #826569

# Submission time Handle Problem Language Result Execution time Memory
826569 2023-08-15T17:07:13 Z arnold518 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2047 ms 1443696 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 4e5;
const ll INF = 1e18;

int N;
int S[MAXN+10], P[MAXN+10], W[MAXN+10], L[MAXN+10];

int A[300][MAXN+10], B[300][MAXN+10], C[300][MAXN+10];
ll D[MAXN+10];

int f(int i, int j)
{
	return i*(i+1)/2+j;
}

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L)
{
	N=_N;
	for(int i=1; i<=N; i++)
	{
		S[i]=_S[i-1]; P[i]=_P[i-1];
		W[i]=_W[i-1]+1; L[i]=_L[i-1]+1;
	}

	for(int i=0; i<=23; i++)
	{
		int p=f(i, 0);
		for(int j=1; j<=N; j++)
		{
			if(S[j]<(1<<i)) A[p][j]=S[j], B[p][j]=(1<<(i+1)), C[p][j]=W[j];
			else if(S[j]<(1<<(i+1))) A[p][j]=P[j], B[p][j]=min((1<<(i+1)), S[j]), C[p][j]=L[j];
			else A[p][j]=P[j], B[p][j]=(1<<(i+1)), C[p][j]=L[j];
		}
		A[p][N+1]=0, B[p][N+1]=0; C[p][N+1]=N+1;

		for(int j=1; j<=i; j++)
		{
			p=f(i, j);
			for(int k=1; k<=N+1; k++)
			{
				C[p][k]=C[p-1][C[p-1][k]];
				A[p][k]=A[p-1][k]+A[p-1][C[p-1][k]];
				B[p][k]=min(B[p-1][k], B[p-1][C[p-1][k]]-A[p-1][k]);
			}
		}
	}

	for(int i=N; i>=0; i--) D[i]=D[W[i]]+S[i];
}

ll simulate(int now, int _x)
{
	now++;
	ll x=_x;

	for(int i=0; i<=23; i++)
	{
		if(x>=(1<<(i+1))) continue;
		for(int j=i; j>=0; j--)
		{
			int p=f(i, j);
			if(x<B[p][now])
			{
				x+=A[p][now];
				now=C[p][now];
			}
		}
		if(now>N) break;
		if(x<(1<<(i+1)))
		{
			if(x>=S[now]) x+=S[now], now=W[now];
			else x+=P[now], now=L[now];
		}
	}
	return x+D[now];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 7 ms 13808 KB Output is correct
4 Correct 108 ms 185136 KB Output is correct
5 Correct 7 ms 13712 KB Output is correct
6 Correct 107 ms 185104 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 956 ms 1431956 KB Output is correct
3 Correct 893 ms 1438860 KB Output is correct
4 Correct 1038 ms 1440448 KB Output is correct
5 Correct 860 ms 1440488 KB Output is correct
6 Correct 2024 ms 1438872 KB Output is correct
7 Correct 1858 ms 1437100 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 168 ms 186060 KB Output is correct
3 Correct 143 ms 185940 KB Output is correct
4 Correct 152 ms 185932 KB Output is correct
5 Correct 159 ms 185988 KB Output is correct
6 Correct 411 ms 185888 KB Output is correct
7 Correct 309 ms 185932 KB Output is correct
8 Correct 255 ms 185900 KB Output is correct
9 Correct 143 ms 185868 KB Output is correct
10 Correct 270 ms 185888 KB Output is correct
11 Correct 273 ms 185952 KB Output is correct
12 Correct 488 ms 185868 KB Output is correct
13 Correct 485 ms 185948 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 168 ms 186060 KB Output is correct
3 Correct 143 ms 185940 KB Output is correct
4 Correct 152 ms 185932 KB Output is correct
5 Correct 159 ms 185988 KB Output is correct
6 Correct 411 ms 185888 KB Output is correct
7 Correct 309 ms 185932 KB Output is correct
8 Correct 255 ms 185900 KB Output is correct
9 Correct 143 ms 185868 KB Output is correct
10 Correct 270 ms 185888 KB Output is correct
11 Correct 273 ms 185952 KB Output is correct
12 Correct 488 ms 185868 KB Output is correct
13 Correct 485 ms 185948 KB Output is correct
14 Correct 6 ms 10196 KB Output is correct
15 Correct 156 ms 186016 KB Output is correct
16 Correct 162 ms 185936 KB Output is correct
17 Correct 242 ms 185928 KB Output is correct
18 Correct 250 ms 185932 KB Output is correct
19 Correct 409 ms 185944 KB Output is correct
20 Correct 424 ms 185932 KB Output is correct
21 Correct 501 ms 185932 KB Output is correct
22 Correct 576 ms 185932 KB Output is correct
23 Correct 334 ms 185948 KB Output is correct
24 Correct 1052 ms 185940 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 168 ms 186060 KB Output is correct
3 Correct 143 ms 185940 KB Output is correct
4 Correct 152 ms 185932 KB Output is correct
5 Correct 159 ms 185988 KB Output is correct
6 Correct 411 ms 185888 KB Output is correct
7 Correct 309 ms 185932 KB Output is correct
8 Correct 255 ms 185900 KB Output is correct
9 Correct 143 ms 185868 KB Output is correct
10 Correct 270 ms 185888 KB Output is correct
11 Correct 273 ms 185952 KB Output is correct
12 Correct 488 ms 185868 KB Output is correct
13 Correct 485 ms 185948 KB Output is correct
14 Correct 6 ms 10196 KB Output is correct
15 Correct 156 ms 186016 KB Output is correct
16 Correct 162 ms 185936 KB Output is correct
17 Correct 242 ms 185928 KB Output is correct
18 Correct 250 ms 185932 KB Output is correct
19 Correct 409 ms 185944 KB Output is correct
20 Correct 424 ms 185932 KB Output is correct
21 Correct 501 ms 185932 KB Output is correct
22 Correct 576 ms 185932 KB Output is correct
23 Correct 334 ms 185948 KB Output is correct
24 Correct 1052 ms 185940 KB Output is correct
25 Correct 115 ms 185136 KB Output is correct
26 Correct 161 ms 185932 KB Output is correct
27 Correct 145 ms 186028 KB Output is correct
28 Correct 143 ms 185972 KB Output is correct
29 Correct 176 ms 185980 KB Output is correct
30 Correct 471 ms 185904 KB Output is correct
31 Correct 616 ms 185884 KB Output is correct
32 Correct 675 ms 185932 KB Output is correct
33 Correct 411 ms 185864 KB Output is correct
34 Correct 1179 ms 185804 KB Output is correct
35 Correct 582 ms 185948 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10196 KB Output is correct
2 Correct 956 ms 1431956 KB Output is correct
3 Correct 893 ms 1438860 KB Output is correct
4 Correct 1038 ms 1440448 KB Output is correct
5 Correct 860 ms 1440488 KB Output is correct
6 Correct 2024 ms 1438872 KB Output is correct
7 Correct 1858 ms 1437100 KB Output is correct
8 Correct 5 ms 10196 KB Output is correct
9 Correct 168 ms 186060 KB Output is correct
10 Correct 143 ms 185940 KB Output is correct
11 Correct 152 ms 185932 KB Output is correct
12 Correct 159 ms 185988 KB Output is correct
13 Correct 411 ms 185888 KB Output is correct
14 Correct 309 ms 185932 KB Output is correct
15 Correct 255 ms 185900 KB Output is correct
16 Correct 143 ms 185868 KB Output is correct
17 Correct 270 ms 185888 KB Output is correct
18 Correct 273 ms 185952 KB Output is correct
19 Correct 488 ms 185868 KB Output is correct
20 Correct 485 ms 185948 KB Output is correct
21 Correct 6 ms 10196 KB Output is correct
22 Correct 156 ms 186016 KB Output is correct
23 Correct 162 ms 185936 KB Output is correct
24 Correct 242 ms 185928 KB Output is correct
25 Correct 250 ms 185932 KB Output is correct
26 Correct 409 ms 185944 KB Output is correct
27 Correct 424 ms 185932 KB Output is correct
28 Correct 501 ms 185932 KB Output is correct
29 Correct 576 ms 185932 KB Output is correct
30 Correct 334 ms 185948 KB Output is correct
31 Correct 1052 ms 185940 KB Output is correct
32 Correct 115 ms 185136 KB Output is correct
33 Correct 161 ms 185932 KB Output is correct
34 Correct 145 ms 186028 KB Output is correct
35 Correct 143 ms 185972 KB Output is correct
36 Correct 176 ms 185980 KB Output is correct
37 Correct 471 ms 185904 KB Output is correct
38 Correct 616 ms 185884 KB Output is correct
39 Correct 675 ms 185932 KB Output is correct
40 Correct 411 ms 185864 KB Output is correct
41 Correct 1179 ms 185804 KB Output is correct
42 Correct 582 ms 185948 KB Output is correct
43 Correct 3 ms 6612 KB Output is correct
44 Correct 5 ms 10224 KB Output is correct
45 Correct 1164 ms 1443696 KB Output is correct
46 Correct 840 ms 1439016 KB Output is correct
47 Correct 863 ms 1439436 KB Output is correct
48 Correct 892 ms 1441560 KB Output is correct
49 Correct 1080 ms 1443656 KB Output is correct
50 Correct 1475 ms 1441248 KB Output is correct
51 Correct 875 ms 1441668 KB Output is correct
52 Correct 1590 ms 1439220 KB Output is correct
53 Correct 1926 ms 1440140 KB Output is correct
54 Correct 1286 ms 1441220 KB Output is correct
55 Correct 2047 ms 1440120 KB Output is correct
56 Correct 1893 ms 1440820 KB Output is correct
57 Correct 1858 ms 1440868 KB Output is correct
58 Correct 1918 ms 1440880 KB Output is correct
59 Correct 1891 ms 1441160 KB Output is correct
60 Correct 1516 ms 1440292 KB Output is correct
61 Correct 1428 ms 1440320 KB Output is correct