oj.uz

답안 #443537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443537 2021-07-10T17:32:17 Z JvThunder 던전 (IOI21_dungeons) C++17
100 / 100
 2796 ms 915540 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
typedef long long ll;
using namespace std;
int bs = 5;
const int nop = 5;
const int noa = 19;
int IN = 1e9+7;
ll a[400005] = {0};
pair<int,pair<int,ll>> jump[nop][noa][400005];
int N;
vector<int> S,P,W,L; 
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	S = s; P = p; W = w; L = l; N = n;
	S.push_back(IN);
	P.push_back(IN);
	W.push_back(n);
	L.push_back(n);
	for(int i=n-1; i>=0; i--) a[i] = a[W[i]] + S[i];
	for(int ph=0; ph<nop; ph++)
	{
		ll l = 1<<(bs*ph);
		ll r = 1<<(bs*(ph+1));

		for(int i=0; i<=n; i++) 
		{
			if ((l<S[i] && S[i]<r) || i==n) jump[ph][0][i] = {L[i], {S[i], P[i]}};
			else if (S[i]<=l) jump[ph][0][i] = {W[i], {IN, S[i]}};
			else jump[ph][0][i] = {L[i], {IN, P[i]}};
		}
		for(int b=1; b<noa; b++)
		{
			for (int i=0; i<=n; i++)
			{
				int pos = i;
				ll min_S = IN, str_a = 0;
				for (int it=0; it<2; it++)
				{
					auto pr = jump[ph][b-1][pos];
					min_S = min(min_S, pr.sc.fr-str_a);
					str_a += pr.sc.sc;
					pos = pr.fr;
				}
				jump[ph][b][i] = {pos, {min_S, str_a}};
			}
		}
	}
	return;
}
ll simulate(int x, int z) 
{
	int pos = x;
	ll str = z;
	for(int a=0; a<nop; a++)
	{
		ll l = 1<<(bs*a);
		ll r = 1<<(bs*(a+1));
		while(pos!=N && l<=str && str<r)
		{
			for(int b=noa-1; b>=0; b--)
			{
				while(str+jump[a][b][pos].sc.sc < r && str-jump[a][b][pos].sc.fr < 0)
				{
					str += jump[a][b][pos].sc.sc;
					pos = jump[a][b][pos].fr;
				}
			}
			if(pos!=N)
			{
				if(str>=S[pos]) str += S[pos], pos = W[pos];
				else str += P[pos], pos = L[pos];
			}
		}
	}
	str += a[pos];
	return str;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 1 ms 972 KB Output is correct
3 Correct 6 ms 5580 KB Output is correct
4 Correct 97 ms 115296 KB Output is correct
5 Correct 4 ms 5580 KB Output is correct
6 Correct 90 ms 115252 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 801 ms 915388 KB Output is correct
3 Correct 776 ms 915380 KB Output is correct
4 Correct 810 ms 915540 KB Output is correct
5 Correct 800 ms 915416 KB Output is correct
6 Correct 1050 ms 915528 KB Output is correct
7 Correct 929 ms 915264 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 235 ms 116152 KB Output is correct
3 Correct 173 ms 116108 KB Output is correct
4 Correct 152 ms 116116 KB Output is correct
5 Correct 125 ms 116164 KB Output is correct
6 Correct 315 ms 116020 KB Output is correct
7 Correct 291 ms 116032 KB Output is correct
8 Correct 211 ms 116092 KB Output is correct
9 Correct 144 ms 116116 KB Output is correct
10 Correct 230 ms 116108 KB Output is correct
11 Correct 323 ms 116108 KB Output is correct
12 Correct 638 ms 116020 KB Output is correct
13 Correct 616 ms 116020 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 235 ms 116152 KB Output is correct
3 Correct 173 ms 116108 KB Output is correct
4 Correct 152 ms 116116 KB Output is correct
5 Correct 125 ms 116164 KB Output is correct
6 Correct 315 ms 116020 KB Output is correct
7 Correct 291 ms 116032 KB Output is correct
8 Correct 211 ms 116092 KB Output is correct
9 Correct 144 ms 116116 KB Output is correct
10 Correct 230 ms 116108 KB Output is correct
11 Correct 323 ms 116108 KB Output is correct
12 Correct 638 ms 116020 KB Output is correct
13 Correct 616 ms 116020 KB Output is correct
14 Correct 3 ms 3324 KB Output is correct
15 Correct 136 ms 116092 KB Output is correct
16 Correct 193 ms 116036 KB Output is correct
17 Correct 128 ms 116040 KB Output is correct
18 Correct 160 ms 116036 KB Output is correct
19 Correct 291 ms 116048 KB Output is correct
20 Correct 189 ms 116084 KB Output is correct
21 Correct 221 ms 116020 KB Output is correct
22 Correct 353 ms 116044 KB Output is correct
23 Correct 342 ms 116132 KB Output is correct
24 Correct 363 ms 116112 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 235 ms 116152 KB Output is correct
3 Correct 173 ms 116108 KB Output is correct
4 Correct 152 ms 116116 KB Output is correct
5 Correct 125 ms 116164 KB Output is correct
6 Correct 315 ms 116020 KB Output is correct
7 Correct 291 ms 116032 KB Output is correct
8 Correct 211 ms 116092 KB Output is correct
9 Correct 144 ms 116116 KB Output is correct
10 Correct 230 ms 116108 KB Output is correct
11 Correct 323 ms 116108 KB Output is correct
12 Correct 638 ms 116020 KB Output is correct
13 Correct 616 ms 116020 KB Output is correct
14 Correct 3 ms 3324 KB Output is correct
15 Correct 136 ms 116092 KB Output is correct
16 Correct 193 ms 116036 KB Output is correct
17 Correct 128 ms 116040 KB Output is correct
18 Correct 160 ms 116036 KB Output is correct
19 Correct 291 ms 116048 KB Output is correct
20 Correct 189 ms 116084 KB Output is correct
21 Correct 221 ms 116020 KB Output is correct
22 Correct 353 ms 116044 KB Output is correct
23 Correct 342 ms 116132 KB Output is correct
24 Correct 363 ms 116112 KB Output is correct
25 Correct 98 ms 115248 KB Output is correct
26 Correct 215 ms 116080 KB Output is correct
27 Correct 141 ms 116040 KB Output is correct
28 Correct 132 ms 116144 KB Output is correct
29 Correct 256 ms 116032 KB Output is correct
30 Correct 227 ms 116052 KB Output is correct
31 Correct 241 ms 116020 KB Output is correct
32 Correct 320 ms 116064 KB Output is correct
33 Correct 735 ms 116020 KB Output is correct
34 Correct 1278 ms 116024 KB Output is correct
35 Correct 736 ms 116020 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 801 ms 915388 KB Output is correct
3 Correct 776 ms 915380 KB Output is correct
4 Correct 810 ms 915540 KB Output is correct
5 Correct 800 ms 915416 KB Output is correct
6 Correct 1050 ms 915528 KB Output is correct
7 Correct 929 ms 915264 KB Output is correct
8 Correct 3 ms 3276 KB Output is correct
9 Correct 235 ms 116152 KB Output is correct
10 Correct 173 ms 116108 KB Output is correct
11 Correct 152 ms 116116 KB Output is correct
12 Correct 125 ms 116164 KB Output is correct
13 Correct 315 ms 116020 KB Output is correct
14 Correct 291 ms 116032 KB Output is correct
15 Correct 211 ms 116092 KB Output is correct
16 Correct 144 ms 116116 KB Output is correct
17 Correct 230 ms 116108 KB Output is correct
18 Correct 323 ms 116108 KB Output is correct
19 Correct 638 ms 116020 KB Output is correct
20 Correct 616 ms 116020 KB Output is correct
21 Correct 3 ms 3324 KB Output is correct
22 Correct 136 ms 116092 KB Output is correct
23 Correct 193 ms 116036 KB Output is correct
24 Correct 128 ms 116040 KB Output is correct
25 Correct 160 ms 116036 KB Output is correct
26 Correct 291 ms 116048 KB Output is correct
27 Correct 189 ms 116084 KB Output is correct
28 Correct 221 ms 116020 KB Output is correct
29 Correct 353 ms 116044 KB Output is correct
30 Correct 342 ms 116132 KB Output is correct
31 Correct 363 ms 116112 KB Output is correct
32 Correct 98 ms 115248 KB Output is correct
33 Correct 215 ms 116080 KB Output is correct
34 Correct 141 ms 116040 KB Output is correct
35 Correct 132 ms 116144 KB Output is correct
36 Correct 256 ms 116032 KB Output is correct
37 Correct 227 ms 116052 KB Output is correct
38 Correct 241 ms 116020 KB Output is correct
39 Correct 320 ms 116064 KB Output is correct
40 Correct 735 ms 116020 KB Output is correct
41 Correct 1278 ms 116024 KB Output is correct
42 Correct 736 ms 116020 KB Output is correct
43 Correct 1 ms 972 KB Output is correct
44 Correct 4 ms 3276 KB Output is correct
45 Correct 1133 ms 915440 KB Output is correct
46 Correct 810 ms 915384 KB Output is correct
47 Correct 833 ms 915392 KB Output is correct
48 Correct 851 ms 915428 KB Output is correct
49 Correct 1194 ms 915388 KB Output is correct
50 Correct 939 ms 915416 KB Output is correct
51 Correct 835 ms 915312 KB Output is correct
52 Correct 921 ms 915420 KB Output is correct
53 Correct 1673 ms 915412 KB Output is correct
54 Correct 1754 ms 915408 KB Output is correct
55 Correct 2208 ms 915392 KB Output is correct
56 Correct 2242 ms 915332 KB Output is correct
57 Correct 2796 ms 915388 KB Output is correct
58 Correct 2671 ms 915408 KB Output is correct
59 Correct 2511 ms 915356 KB Output is correct
60 Correct 2325 ms 915400 KB Output is correct
61 Correct 2370 ms 915464 KB Output is correct