oj.uz

Submission #609055

# Submission time Handle Problem Language Result Execution time Memory
609055 2022-07-27T11:59:34 Z asdfasdfasdfasdf Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2166 ms 542828 KB 
#include "dungeons.h"

#include <bits/stdc++.h>

using namespace std;

#define MAX 444444

int N;

vector<int> S,P,win,lose;

vector<int> v[MAX];

const int INF=1e9;

int Next[8][25][MAX];
int Sum[8][25][MAX];
int Value[8][25][MAX];
long long dp[MAX];

void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l)
{
    tie(N,S,P,win,lose)=make_tuple(n,s,p,w,l);
	for(int i=n-1;i>=0;i--)
        dp[i]=dp[w[i]]+s[i];
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<n;j++)
		{
		    int L=(1<<(3*i));
			if(s[j]<L)
			{
				Next[i][0][j]=w[j];
				Sum[i][0][j]=s[j];
				Value[i][0][j]=INF;
			}
			else
			{
				Next[i][0][j]=l[j];
				Sum[i][0][j]=p[j];
				Value[i][0][j]=s[j];
			}
		}
		Next[i][0][n]=n;
		Sum[i][0][n]=INF;
		Value[i][0][n]=INF;
		for(int j=1;j<3*i+3;j++)
		{
			for(int k=0;k<=n;k++)
            {
				Next[i][j][k]=Next[i][j-1][Next[i][j-1][k]];
				Sum[i][j][k]=Sum[i][j-1][k]+Sum[i][j-1][Next[i][j-1][k]];
				Sum[i][j][k]=min(Sum[i][j][k],INF);
				Value[i][j][k]=min(Value[i][j-1][k],Value[i][j-1][Next[i][j-1][k]]-Sum[i][j-1][k]);
				Value[i][j][k]=max(Value[i][j][k],0);
			}
		}
	}
	return;
}

long long simulate(int x, int z)
{
	long long Z=z;
	for(int i=0;i<8;i++)
    {
		while(Z<(1<<(3*i+3)))
		{
			for(int j=3*i+2;j>=0;j--)
			{
				if(Next[i][j][x]!=N && Z+Sum[i][j][x]<(1<<(3*i+3)) && Value[i][j][x]>Z)
				{
					Z+=Sum[i][j][x];
					x=Next[i][j][x];
				}
			}
			if(x!=N && Z<(1<<(3*i+3)) && (S[x]>Z || S[x]<(1<<(2*i))))
            {
				Z+=Sum[i][0][x];
				x=Next[i][0][x];
			}
			if(x==N)
				break;
			if(S[x]<=Z)
            {
				Z+=S[x];
				x=win[x];
			}
			if(x==N)
                break;
		}
	}
	return Z+dp[x];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13140 KB Output is correct
2 Correct 7 ms 13056 KB Output is correct
3 Correct 9 ms 15840 KB Output is correct
4 Correct 92 ms 79664 KB Output is correct
5 Correct 14 ms 15808 KB Output is correct
6 Correct 71 ms 79648 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 532 ms 542672 KB Output is correct
3 Correct 638 ms 542672 KB Output is correct
4 Correct 703 ms 542688 KB Output is correct
5 Correct 670 ms 542628 KB Output is correct
6 Correct 871 ms 542620 KB Output is correct
7 Correct 859 ms 542676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 142 ms 80168 KB Output is correct
3 Correct 114 ms 80456 KB Output is correct
4 Correct 90 ms 80312 KB Output is correct
5 Correct 102 ms 80212 KB Output is correct
6 Correct 300 ms 80360 KB Output is correct
7 Correct 243 ms 80256 KB Output is correct
8 Correct 195 ms 80180 KB Output is correct
9 Correct 110 ms 80296 KB Output is correct
10 Correct 187 ms 80328 KB Output is correct
11 Correct 269 ms 80240 KB Output is correct
12 Correct 543 ms 80308 KB Output is correct
13 Correct 522 ms 80348 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 142 ms 80168 KB Output is correct
3 Correct 114 ms 80456 KB Output is correct
4 Correct 90 ms 80312 KB Output is correct
5 Correct 102 ms 80212 KB Output is correct
6 Correct 300 ms 80360 KB Output is correct
7 Correct 243 ms 80256 KB Output is correct
8 Correct 195 ms 80180 KB Output is correct
9 Correct 110 ms 80296 KB Output is correct
10 Correct 187 ms 80328 KB Output is correct
11 Correct 269 ms 80240 KB Output is correct
12 Correct 543 ms 80308 KB Output is correct
13 Correct 522 ms 80348 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 108 ms 80344 KB Output is correct
16 Correct 128 ms 80376 KB Output is correct
17 Correct 108 ms 80168 KB Output is correct
18 Correct 145 ms 80200 KB Output is correct
19 Correct 213 ms 80408 KB Output is correct
20 Correct 178 ms 80212 KB Output is correct
21 Correct 235 ms 80200 KB Output is correct
22 Correct 175 ms 80312 KB Output is correct
23 Correct 286 ms 80384 KB Output is correct
24 Correct 393 ms 80228 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 142 ms 80168 KB Output is correct
3 Correct 114 ms 80456 KB Output is correct
4 Correct 90 ms 80312 KB Output is correct
5 Correct 102 ms 80212 KB Output is correct
6 Correct 300 ms 80360 KB Output is correct
7 Correct 243 ms 80256 KB Output is correct
8 Correct 195 ms 80180 KB Output is correct
9 Correct 110 ms 80296 KB Output is correct
10 Correct 187 ms 80328 KB Output is correct
11 Correct 269 ms 80240 KB Output is correct
12 Correct 543 ms 80308 KB Output is correct
13 Correct 522 ms 80348 KB Output is correct
14 Correct 9 ms 14420 KB Output is correct
15 Correct 108 ms 80344 KB Output is correct
16 Correct 128 ms 80376 KB Output is correct
17 Correct 108 ms 80168 KB Output is correct
18 Correct 145 ms 80200 KB Output is correct
19 Correct 213 ms 80408 KB Output is correct
20 Correct 178 ms 80212 KB Output is correct
21 Correct 235 ms 80200 KB Output is correct
22 Correct 175 ms 80312 KB Output is correct
23 Correct 286 ms 80384 KB Output is correct
24 Correct 393 ms 80228 KB Output is correct
25 Correct 67 ms 79380 KB Output is correct
26 Correct 126 ms 80100 KB Output is correct
27 Correct 109 ms 80028 KB Output is correct
28 Correct 109 ms 80080 KB Output is correct
29 Correct 135 ms 80204 KB Output is correct
30 Correct 178 ms 80080 KB Output is correct
31 Correct 292 ms 80160 KB Output is correct
32 Correct 341 ms 80096 KB Output is correct
33 Correct 507 ms 80052 KB Output is correct
34 Correct 985 ms 80132 KB Output is correct
35 Correct 464 ms 80088 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 532 ms 542672 KB Output is correct
3 Correct 638 ms 542672 KB Output is correct
4 Correct 703 ms 542688 KB Output is correct
5 Correct 670 ms 542628 KB Output is correct
6 Correct 871 ms 542620 KB Output is correct
7 Correct 859 ms 542676 KB Output is correct
8 Correct 8 ms 14420 KB Output is correct
9 Correct 142 ms 80168 KB Output is correct
10 Correct 114 ms 80456 KB Output is correct
11 Correct 90 ms 80312 KB Output is correct
12 Correct 102 ms 80212 KB Output is correct
13 Correct 300 ms 80360 KB Output is correct
14 Correct 243 ms 80256 KB Output is correct
15 Correct 195 ms 80180 KB Output is correct
16 Correct 110 ms 80296 KB Output is correct
17 Correct 187 ms 80328 KB Output is correct
18 Correct 269 ms 80240 KB Output is correct
19 Correct 543 ms 80308 KB Output is correct
20 Correct 522 ms 80348 KB Output is correct
21 Correct 9 ms 14420 KB Output is correct
22 Correct 108 ms 80344 KB Output is correct
23 Correct 128 ms 80376 KB Output is correct
24 Correct 108 ms 80168 KB Output is correct
25 Correct 145 ms 80200 KB Output is correct
26 Correct 213 ms 80408 KB Output is correct
27 Correct 178 ms 80212 KB Output is correct
28 Correct 235 ms 80200 KB Output is correct
29 Correct 175 ms 80312 KB Output is correct
30 Correct 286 ms 80384 KB Output is correct
31 Correct 393 ms 80228 KB Output is correct
32 Correct 67 ms 79380 KB Output is correct
33 Correct 126 ms 80100 KB Output is correct
34 Correct 109 ms 80028 KB Output is correct
35 Correct 109 ms 80080 KB Output is correct
36 Correct 135 ms 80204 KB Output is correct
37 Correct 178 ms 80080 KB Output is correct
38 Correct 292 ms 80160 KB Output is correct
39 Correct 341 ms 80096 KB Output is correct
40 Correct 507 ms 80052 KB Output is correct
41 Correct 985 ms 80132 KB Output is correct
42 Correct 464 ms 80088 KB Output is correct
43 Correct 9 ms 13140 KB Output is correct
44 Correct 9 ms 14472 KB Output is correct
45 Correct 781 ms 542464 KB Output is correct
46 Correct 504 ms 542412 KB Output is correct
47 Correct 527 ms 542404 KB Output is correct
48 Correct 602 ms 542460 KB Output is correct
49 Correct 672 ms 542828 KB Output is correct
50 Correct 649 ms 542720 KB Output is correct
51 Correct 514 ms 542656 KB Output is correct
52 Correct 748 ms 542620 KB Output is correct
53 Correct 1235 ms 542780 KB Output is correct
54 Correct 1303 ms 542540 KB Output is correct
55 Correct 1804 ms 542136 KB Output is correct
56 Correct 1772 ms 542140 KB Output is correct
57 Correct 2166 ms 542268 KB Output is correct
58 Correct 1555 ms 542168 KB Output is correct
59 Correct 1855 ms 542368 KB Output is correct
60 Correct 1201 ms 542200 KB Output is correct
61 Correct 1208 ms 542240 KB Output is correct