oj.uz

답안 #645195

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
645195 2022-09-26T12:08:07 Z jamezzz 던전 (IOI21_dungeons) C++17
100 / 100
 2809 ms 730564 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

typedef long long ll;

#define maxn 400001
#define lgn 9
#define base 6
#define INF 1023456789123456789

int n,to[lgn+1][lgn][maxn];
ll gain[lgn+1][lgn][maxn],mn[lgn+1][lgn][maxn],pwr[lgn+2];
vector<int> s,w;

void init(int _n,vector<int> _s,vector<int> p,vector<int> _w,vector<int> l){
	pwr[0]=1;
	for(int i=1;i<=lgn+1;++i)pwr[i]=pwr[i-1]*base;
	n=_n;s=_s;w=_w;
	for(int k=0;k<=lgn;++k){//win if <base^k, lose if >=base^k
		for(int i=0;i<n;++i){
			to[k][0][i]=(s[i]<pwr[k])?w[i]:l[i];
			gain[k][0][i]=(s[i]<pwr[k])?s[i]:p[i];
			mn[k][0][i]=(s[i]<pwr[k])?INF:s[i];
		}
		to[k][0][n]=n;
		gain[k][0][n]=0;
		mn[k][0][n]=INF;
		for(int j=1;j<lgn;++j){
			for(int i=0;i<=n;++i){
				int cur=i;
				mn[k][j][i]=INF;
				for(int b=0;b<base;++b){
					to[k][j][i]=to[k][j-1][cur];
					mn[k][j][i]=min(mn[k][j][i],mn[k][j-1][cur]-gain[k][j][i]);
					gain[k][j][i]+=gain[k][j-1][cur];
					cur=to[k][j-1][cur];
					if(cur==n)break;
				}
			}
		}
	}
}

ll simulate(int x,int z){
	ll str=z;
	int pos=x;
	while(pos!=n){
		int k=0;
		while(pwr[k+1]<=str)++k;
		if(k>lgn){
			int cur=pos;
			for(int b=0;b<base-1;++b){
				str+=gain[lgn][lgn-1][cur];
				cur=to[lgn][lgn-1][pos];
				if(cur==n)break;
			}
			return str;
		}
		for(int j=lgn-1;j>=0;--j){
			for(int b=0;b<base-1;++b){
				if(str<mn[k][j][pos]){
					str+=gain[k][j][pos];
					pos=to[k][j][pos];
				}
				else break;
			}
		}
		if(pos!=n){
			str+=s[pos];
			pos=w[pos];
		}
	}
	return str;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 4 ms 5948 KB Output is correct
4 Correct 103 ms 93392 KB Output is correct
5 Correct 5 ms 5972 KB Output is correct
6 Correct 102 ms 93252 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4180 KB Output is correct
2 Correct 866 ms 728088 KB Output is correct
3 Correct 925 ms 728120 KB Output is correct
4 Correct 835 ms 729640 KB Output is correct
5 Correct 941 ms 729736 KB Output is correct
6 Correct 885 ms 728052 KB Output is correct
7 Correct 850 ms 726348 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 163 ms 94712 KB Output is correct
3 Correct 135 ms 94916 KB Output is correct
4 Correct 122 ms 94268 KB Output is correct
5 Correct 112 ms 94156 KB Output is correct
6 Correct 202 ms 94412 KB Output is correct
7 Correct 210 ms 94408 KB Output is correct
8 Correct 121 ms 94044 KB Output is correct
9 Correct 125 ms 94056 KB Output is correct
10 Correct 116 ms 94032 KB Output is correct
11 Correct 180 ms 94424 KB Output is correct
12 Correct 310 ms 94416 KB Output is correct
13 Correct 198 ms 94404 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 163 ms 94712 KB Output is correct
3 Correct 135 ms 94916 KB Output is correct
4 Correct 122 ms 94268 KB Output is correct
5 Correct 112 ms 94156 KB Output is correct
6 Correct 202 ms 94412 KB Output is correct
7 Correct 210 ms 94408 KB Output is correct
8 Correct 121 ms 94044 KB Output is correct
9 Correct 125 ms 94056 KB Output is correct
10 Correct 116 ms 94032 KB Output is correct
11 Correct 180 ms 94424 KB Output is correct
12 Correct 310 ms 94416 KB Output is correct
13 Correct 198 ms 94404 KB Output is correct
14 Correct 4 ms 4180 KB Output is correct
15 Correct 137 ms 94544 KB Output is correct
16 Correct 174 ms 94788 KB Output is correct
17 Correct 143 ms 94224 KB Output is correct
18 Correct 127 ms 94276 KB Output is correct
19 Correct 200 ms 94368 KB Output is correct
20 Correct 148 ms 94164 KB Output is correct
21 Correct 145 ms 94208 KB Output is correct
22 Correct 116 ms 94244 KB Output is correct
23 Correct 179 ms 94408 KB Output is correct
24 Correct 297 ms 94392 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4180 KB Output is correct
2 Correct 163 ms 94712 KB Output is correct
3 Correct 135 ms 94916 KB Output is correct
4 Correct 122 ms 94268 KB Output is correct
5 Correct 112 ms 94156 KB Output is correct
6 Correct 202 ms 94412 KB Output is correct
7 Correct 210 ms 94408 KB Output is correct
8 Correct 121 ms 94044 KB Output is correct
9 Correct 125 ms 94056 KB Output is correct
10 Correct 116 ms 94032 KB Output is correct
11 Correct 180 ms 94424 KB Output is correct
12 Correct 310 ms 94416 KB Output is correct
13 Correct 198 ms 94404 KB Output is correct
14 Correct 4 ms 4180 KB Output is correct
15 Correct 137 ms 94544 KB Output is correct
16 Correct 174 ms 94788 KB Output is correct
17 Correct 143 ms 94224 KB Output is correct
18 Correct 127 ms 94276 KB Output is correct
19 Correct 200 ms 94368 KB Output is correct
20 Correct 148 ms 94164 KB Output is correct
21 Correct 145 ms 94208 KB Output is correct
22 Correct 116 ms 94244 KB Output is correct
23 Correct 179 ms 94408 KB Output is correct
24 Correct 297 ms 94392 KB Output is correct
25 Correct 129 ms 93732 KB Output is correct
26 Correct 159 ms 94796 KB Output is correct
27 Correct 136 ms 94236 KB Output is correct
28 Correct 141 ms 94276 KB Output is correct
29 Correct 172 ms 94668 KB Output is correct
30 Correct 177 ms 94328 KB Output is correct
31 Correct 164 ms 94072 KB Output is correct
32 Correct 290 ms 94280 KB Output is correct
33 Correct 298 ms 94396 KB Output is correct
34 Correct 745 ms 94152 KB Output is correct
35 Correct 374 ms 94272 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4180 KB Output is correct
2 Correct 866 ms 728088 KB Output is correct
3 Correct 925 ms 728120 KB Output is correct
4 Correct 835 ms 729640 KB Output is correct
5 Correct 941 ms 729736 KB Output is correct
6 Correct 885 ms 728052 KB Output is correct
7 Correct 850 ms 726348 KB Output is correct
8 Correct 4 ms 4180 KB Output is correct
9 Correct 163 ms 94712 KB Output is correct
10 Correct 135 ms 94916 KB Output is correct
11 Correct 122 ms 94268 KB Output is correct
12 Correct 112 ms 94156 KB Output is correct
13 Correct 202 ms 94412 KB Output is correct
14 Correct 210 ms 94408 KB Output is correct
15 Correct 121 ms 94044 KB Output is correct
16 Correct 125 ms 94056 KB Output is correct
17 Correct 116 ms 94032 KB Output is correct
18 Correct 180 ms 94424 KB Output is correct
19 Correct 310 ms 94416 KB Output is correct
20 Correct 198 ms 94404 KB Output is correct
21 Correct 4 ms 4180 KB Output is correct
22 Correct 137 ms 94544 KB Output is correct
23 Correct 174 ms 94788 KB Output is correct
24 Correct 143 ms 94224 KB Output is correct
25 Correct 127 ms 94276 KB Output is correct
26 Correct 200 ms 94368 KB Output is correct
27 Correct 148 ms 94164 KB Output is correct
28 Correct 145 ms 94208 KB Output is correct
29 Correct 116 ms 94244 KB Output is correct
30 Correct 179 ms 94408 KB Output is correct
31 Correct 297 ms 94392 KB Output is correct
32 Correct 129 ms 93732 KB Output is correct
33 Correct 159 ms 94796 KB Output is correct
34 Correct 136 ms 94236 KB Output is correct
35 Correct 141 ms 94276 KB Output is correct
36 Correct 172 ms 94668 KB Output is correct
37 Correct 177 ms 94328 KB Output is correct
38 Correct 164 ms 94072 KB Output is correct
39 Correct 290 ms 94280 KB Output is correct
40 Correct 298 ms 94396 KB Output is correct
41 Correct 745 ms 94152 KB Output is correct
42 Correct 374 ms 94272 KB Output is correct
43 Correct 2 ms 2388 KB Output is correct
44 Correct 4 ms 4164 KB Output is correct
45 Correct 1638 ms 724284 KB Output is correct
46 Correct 1090 ms 725080 KB Output is correct
47 Correct 1145 ms 724860 KB Output is correct
48 Correct 923 ms 724364 KB Output is correct
49 Correct 1834 ms 724088 KB Output is correct
50 Correct 898 ms 722296 KB Output is correct
51 Correct 915 ms 721864 KB Output is correct
52 Correct 964 ms 722092 KB Output is correct
53 Correct 2596 ms 722220 KB Output is correct
54 Correct 1199 ms 730372 KB Output is correct
55 Correct 1832 ms 729404 KB Output is correct
56 Correct 2293 ms 730100 KB Output is correct
57 Correct 2589 ms 730188 KB Output is correct
58 Correct 2442 ms 730564 KB Output is correct
59 Correct 2809 ms 730312 KB Output is correct
60 Correct 2576 ms 729692 KB Output is correct
61 Correct 1793 ms 729444 KB Output is correct