oj.uz

답안 #440318

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
440318 2021-07-02T04:14:54 Z frodakcin 던전 (IOI21_dungeons) C++17
100 / 100
 6324 ms 1592020 KB 
#include "dungeons.h"
#include <cassert>
#include <cstring>
#include <algorithm>
#include <vector>

using ll = long long;

const int MN = 4e5+10;
const int W = 8; // worlds
const int MUL = 11; // multiplier
const int ML = 25; // 2^25 ~ 3e7
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3f;

int N;
std::vector<int> s, p, w, l;
int jmp[W][MN][ML];
ll delta[W][MN][ML], max[W][MN][ML];

void init(int _N, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
	N=_N;
	s=_s, p=_p, w=_w, l=_l;

	memset(jmp, -1, sizeof jmp);
	int b=1;
	for(int v=0;v<W;++v)
	{
		for(int i=0;i<N;++i)
			if(s[i] < b)
			{
				jmp[v][i][0]=w[i];
				delta[v][i][0]=s[i];
				max[v][i][0]=INFL;
			}
			else
			{
				jmp[v][i][0]=l[i];
				delta[v][i][0]=p[i];
				max[v][i][0]=s[i]; // >= max -> unexpected; < max -> go ahead
			}
		for(int j=0;j+1<ML;++j)
			for(int i=0;i<N;++i)
				if(jmp[v][i][j]!=-1 && jmp[v][jmp[v][i][j]][j]!=-1)
				{
					int x = jmp[v][i][j];
					jmp[v][i][j+1]=jmp[v][x][j];
					delta[v][i][j+1]=delta[v][i][j]+delta[v][x][j];
					max[v][i][j+1]=std::min(max[v][i][j], max[v][x][j]-delta[v][i][j]);
				}
		b *= MUL;
	}
}

void step(int &n, ll &z)
{
	if(n==N) return;
	if(z<s[n])
		z+=p[n], n=l[n];
	else
		z+=s[n], n=w[n];
}

void jump(int v, int cut, int &n, ll &z)
{
	for(int i=ML-1;i>=0;--i)
		if(jmp[v][n][i] != -1 && z<max[v][n][i] && (cut == -1 || z+delta[v][n][i]<cut)) // while isn't necessary here
			z+=delta[v][n][i], n=jmp[v][n][i];
}

long long simulate(int n, int _z) {
	ll z=_z;

	int b=1;
	for(int i=0;i+1<W;++i)
	{
		b *= MUL;
		while(z<b)
		{
			jump(i, b, n, z);
			step(n, z);
			if(n==N) return z;
		}
	}
	jump(W-1, -1, n, z);

	assert(n==N);
	return z;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 178 ms 313412 KB Output is correct
2 Correct 166 ms 313596 KB Output is correct
3 Correct 179 ms 319780 KB Output is correct
4 Correct 536 ms 473368 KB Output is correct
5 Correct 181 ms 319868 KB Output is correct
6 Correct 468 ms 473340 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 316740 KB Output is correct
2 Correct 4164 ms 1588604 KB Output is correct
3 Correct 3770 ms 1590876 KB Output is correct
4 Correct 3626 ms 1591228 KB Output is correct
5 Correct 3367 ms 1591400 KB Output is correct
6 Correct 4682 ms 1590108 KB Output is correct
7 Correct 3955 ms 1588924 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 316740 KB Output is correct
2 Correct 677 ms 474740 KB Output is correct
3 Correct 651 ms 474684 KB Output is correct
4 Correct 536 ms 474344 KB Output is correct
5 Correct 612 ms 474260 KB Output is correct
6 Correct 840 ms 474488 KB Output is correct
7 Correct 731 ms 474608 KB Output is correct
8 Correct 718 ms 474216 KB Output is correct
9 Correct 473 ms 474240 KB Output is correct
10 Correct 631 ms 474096 KB Output is correct
11 Correct 882 ms 474472 KB Output is correct
12 Correct 1284 ms 474596 KB Output is correct
13 Correct 1112 ms 474608 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 316740 KB Output is correct
2 Correct 677 ms 474740 KB Output is correct
3 Correct 651 ms 474684 KB Output is correct
4 Correct 536 ms 474344 KB Output is correct
5 Correct 612 ms 474260 KB Output is correct
6 Correct 840 ms 474488 KB Output is correct
7 Correct 731 ms 474608 KB Output is correct
8 Correct 718 ms 474216 KB Output is correct
9 Correct 473 ms 474240 KB Output is correct
10 Correct 631 ms 474096 KB Output is correct
11 Correct 882 ms 474472 KB Output is correct
12 Correct 1284 ms 474596 KB Output is correct
13 Correct 1112 ms 474608 KB Output is correct
14 Correct 184 ms 316632 KB Output is correct
15 Correct 599 ms 474592 KB Output is correct
16 Correct 627 ms 474684 KB Output is correct
17 Correct 675 ms 474336 KB Output is correct
18 Correct 730 ms 474412 KB Output is correct
19 Correct 788 ms 474692 KB Output is correct
20 Correct 751 ms 474268 KB Output is correct
21 Correct 799 ms 474332 KB Output is correct
22 Correct 801 ms 474448 KB Output is correct
23 Correct 892 ms 474608 KB Output is correct
24 Correct 1161 ms 474608 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 316740 KB Output is correct
2 Correct 677 ms 474740 KB Output is correct
3 Correct 651 ms 474684 KB Output is correct
4 Correct 536 ms 474344 KB Output is correct
5 Correct 612 ms 474260 KB Output is correct
6 Correct 840 ms 474488 KB Output is correct
7 Correct 731 ms 474608 KB Output is correct
8 Correct 718 ms 474216 KB Output is correct
9 Correct 473 ms 474240 KB Output is correct
10 Correct 631 ms 474096 KB Output is correct
11 Correct 882 ms 474472 KB Output is correct
12 Correct 1284 ms 474596 KB Output is correct
13 Correct 1112 ms 474608 KB Output is correct
14 Correct 184 ms 316632 KB Output is correct
15 Correct 599 ms 474592 KB Output is correct
16 Correct 627 ms 474684 KB Output is correct
17 Correct 675 ms 474336 KB Output is correct
18 Correct 730 ms 474412 KB Output is correct
19 Correct 788 ms 474692 KB Output is correct
20 Correct 751 ms 474268 KB Output is correct
21 Correct 799 ms 474332 KB Output is correct
22 Correct 801 ms 474448 KB Output is correct
23 Correct 892 ms 474608 KB Output is correct
24 Correct 1161 ms 474608 KB Output is correct
25 Correct 631 ms 473884 KB Output is correct
26 Correct 715 ms 474824 KB Output is correct
27 Correct 576 ms 474292 KB Output is correct
28 Correct 659 ms 474344 KB Output is correct
29 Correct 742 ms 474740 KB Output is correct
30 Correct 890 ms 474612 KB Output is correct
31 Correct 925 ms 474184 KB Output is correct
32 Correct 1027 ms 474340 KB Output is correct
33 Correct 1234 ms 474320 KB Output is correct
34 Correct 1986 ms 474180 KB Output is correct
35 Correct 1036 ms 474600 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 174 ms 316740 KB Output is correct
2 Correct 4164 ms 1588604 KB Output is correct
3 Correct 3770 ms 1590876 KB Output is correct
4 Correct 3626 ms 1591228 KB Output is correct
5 Correct 3367 ms 1591400 KB Output is correct
6 Correct 4682 ms 1590108 KB Output is correct
7 Correct 3955 ms 1588924 KB Output is correct
8 Correct 182 ms 316740 KB Output is correct
9 Correct 677 ms 474740 KB Output is correct
10 Correct 651 ms 474684 KB Output is correct
11 Correct 536 ms 474344 KB Output is correct
12 Correct 612 ms 474260 KB Output is correct
13 Correct 840 ms 474488 KB Output is correct
14 Correct 731 ms 474608 KB Output is correct
15 Correct 718 ms 474216 KB Output is correct
16 Correct 473 ms 474240 KB Output is correct
17 Correct 631 ms 474096 KB Output is correct
18 Correct 882 ms 474472 KB Output is correct
19 Correct 1284 ms 474596 KB Output is correct
20 Correct 1112 ms 474608 KB Output is correct
21 Correct 184 ms 316632 KB Output is correct
22 Correct 599 ms 474592 KB Output is correct
23 Correct 627 ms 474684 KB Output is correct
24 Correct 675 ms 474336 KB Output is correct
25 Correct 730 ms 474412 KB Output is correct
26 Correct 788 ms 474692 KB Output is correct
27 Correct 751 ms 474268 KB Output is correct
28 Correct 799 ms 474332 KB Output is correct
29 Correct 801 ms 474448 KB Output is correct
30 Correct 892 ms 474608 KB Output is correct
31 Correct 1161 ms 474608 KB Output is correct
32 Correct 631 ms 473884 KB Output is correct
33 Correct 715 ms 474824 KB Output is correct
34 Correct 576 ms 474292 KB Output is correct
35 Correct 659 ms 474344 KB Output is correct
36 Correct 742 ms 474740 KB Output is correct
37 Correct 890 ms 474612 KB Output is correct
38 Correct 925 ms 474184 KB Output is correct
39 Correct 1027 ms 474340 KB Output is correct
40 Correct 1234 ms 474320 KB Output is correct
41 Correct 1986 ms 474180 KB Output is correct
42 Correct 1036 ms 474600 KB Output is correct
43 Correct 182 ms 313648 KB Output is correct
44 Correct 167 ms 316712 KB Output is correct
45 Correct 4333 ms 1590268 KB Output is correct
46 Correct 3542 ms 1589532 KB Output is correct
47 Correct 3632 ms 1589648 KB Output is correct
48 Correct 3889 ms 1589688 KB Output is correct
49 Correct 4526 ms 1589524 KB Output is correct
50 Correct 4270 ms 1589392 KB Output is correct
51 Correct 3692 ms 1589156 KB Output is correct
52 Correct 4481 ms 1588300 KB Output is correct
53 Correct 5845 ms 1588368 KB Output is correct
54 Correct 4860 ms 1588336 KB Output is correct
55 Correct 5539 ms 1587652 KB Output is correct
56 Correct 5432 ms 1587568 KB Output is correct
57 Correct 5419 ms 1587096 KB Output is correct
58 Correct 5337 ms 1586564 KB Output is correct
59 Correct 5322 ms 1586292 KB Output is correct
60 Correct 6088 ms 1585508 KB Output is correct
61 Correct 6324 ms 1592020 KB Output is correct