oj.uz

답안 #443532

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
443532 2021-07-10T17:19:28 Z JvThunder 던전 (IOI21_dungeons) C++17
100 / 100
 2518 ms 915516 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;

//constants
int base = 5; // base here means doing in 2^base
			  // use a higher base instead of 2 for the phase ranges to make the memory efficient
			  // note: using a smaller base decreases runtime but increases memory
			  
const int nop = 5; // no of phase
const int noa = 19; // no of ancestor for binlift
const int sz = 400005; // max size of N
int INF = 1e9+7;

ll add[sz] = {0}; // add[i] = str increase if start at i & win all
pair<int,pair<int,ll>> jump[nop][noa][sz]; // store: jump dest, min(str_opp - str_gained), str_inc
										 // jump[a][b][i] is game simulation starting from index i &
										 // jump 2^b steps ahead assuming only win against everything <=8^a

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;

	// add dummy node for index n
	S.push_back(INF);
	P.push_back(INF);
	W.push_back(n);
	L.push_back(n);
	
	// assume always wins
	for(int i=n-1; i>=0; i--) add[i] = add[W[i]] + S[i];

	for(int ph=0; ph<nop; ph++) // ph: phase
	{
		// current phase range
		ll l = 1<<(base*ph);
		ll r = 1<<(base*(ph+1));

		for(int i=0; i<=n; i++) 
		{
			// if in range, assume lose but store its min(str_opp - str_gained)
			if ((l<S[i] && S[i]<r) || i==n) jump[ph][0][i] = {L[i], {S[i], P[i]}};
			// if below range, assume win
			else if (S[i]<=l) jump[ph][0][i] = {W[i], {INF, S[i]}};
			// if above range, assume lose
			else jump[ph][0][i] = {L[i], {INF, P[i]}};
		}
		
		// binlift
		for(int b=1; b<noa; b++) // no of jump = 2^b
		{
			for (int i=0; i<=n; i++)
			{
				int pos = i;
				ll min_S = INF, str_add = 0;
				for (int it=0; it<2; it++) // 2 jumps of 2^(i-1) -> 1 jump of 2^i
				{
					auto pr = jump[ph][b-1][pos];
					min_S = min(min_S, pr.sec.fir-str_add); // min(str_opp - str_gained) of all prefixes up to 2^b jumps
					str_add += pr.sec.sec; // strength inc from 2^b jumps
					pos = pr.first; // landing position after 2^b jumps
				}
				jump[ph][b][i] = {pos, {min_S, str_add}};
			}
		}
	}
	return;
}
 
ll simulate(int x, int z) 
{
	int pos = x; // current position
	ll str = z; // current strength

	for(int a=0; a<nop; a++)
	{
		// current phase range
		ll l = 1<<(base*a);
		ll r = 1<<(base*(a+1));
		while(pos!=N && l<=str && str<r)
		{
			for(int b=noa-1; b>=0; b--) // binlift until 1 step before you can beat a person with a higher phase
			{
				// condition 1 is true if still in current phase range
				// condition 2 is true if no win against a current phase range
				while(str+jump[a][b][pos].sec.sec < r && str-jump[a][b][pos].sec.fir < 0)
				{
					str += jump[a][b][pos].sec.sec;
					pos = jump[a][b][pos].fir;
				}
			}

			if(pos!=N) // simulate 1 move naive
			{
				if(str>=S[pos]) str += S[pos], pos = W[pos];
				else str += P[pos], pos = L[pos];
			}
		}
	}

	str += add[pos]; //assume win all
	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 4 ms 5580 KB Output is correct
4 Correct 93 ms 115288 KB Output is correct
5 Correct 5 ms 5580 KB Output is correct
6 Correct 91 ms 115308 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 810 ms 915288 KB Output is correct
3 Correct 763 ms 915276 KB Output is correct
4 Correct 847 ms 915372 KB Output is correct
5 Correct 835 ms 915436 KB Output is correct
6 Correct 1082 ms 915464 KB Output is correct
7 Correct 965 ms 915388 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 214 ms 116136 KB Output is correct
3 Correct 184 ms 116036 KB Output is correct
4 Correct 125 ms 116064 KB Output is correct
5 Correct 146 ms 116016 KB Output is correct
6 Correct 315 ms 116068 KB Output is correct
7 Correct 293 ms 116036 KB Output is correct
8 Correct 219 ms 116020 KB Output is correct
9 Correct 148 ms 116032 KB Output is correct
10 Correct 239 ms 116020 KB Output is correct
11 Correct 339 ms 116128 KB Output is correct
12 Correct 675 ms 116160 KB Output is correct
13 Correct 581 ms 116136 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 214 ms 116136 KB Output is correct
3 Correct 184 ms 116036 KB Output is correct
4 Correct 125 ms 116064 KB Output is correct
5 Correct 146 ms 116016 KB Output is correct
6 Correct 315 ms 116068 KB Output is correct
7 Correct 293 ms 116036 KB Output is correct
8 Correct 219 ms 116020 KB Output is correct
9 Correct 148 ms 116032 KB Output is correct
10 Correct 239 ms 116020 KB Output is correct
11 Correct 339 ms 116128 KB Output is correct
12 Correct 675 ms 116160 KB Output is correct
13 Correct 581 ms 116136 KB Output is correct
14 Correct 3 ms 3276 KB Output is correct
15 Correct 130 ms 116052 KB Output is correct
16 Correct 193 ms 116100 KB Output is correct
17 Correct 134 ms 116104 KB Output is correct
18 Correct 128 ms 116068 KB Output is correct
19 Correct 301 ms 116044 KB Output is correct
20 Correct 199 ms 116036 KB Output is correct
21 Correct 222 ms 116084 KB Output is correct
22 Correct 357 ms 116044 KB Output is correct
23 Correct 338 ms 116024 KB Output is correct
24 Correct 383 ms 116028 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3276 KB Output is correct
2 Correct 214 ms 116136 KB Output is correct
3 Correct 184 ms 116036 KB Output is correct
4 Correct 125 ms 116064 KB Output is correct
5 Correct 146 ms 116016 KB Output is correct
6 Correct 315 ms 116068 KB Output is correct
7 Correct 293 ms 116036 KB Output is correct
8 Correct 219 ms 116020 KB Output is correct
9 Correct 148 ms 116032 KB Output is correct
10 Correct 239 ms 116020 KB Output is correct
11 Correct 339 ms 116128 KB Output is correct
12 Correct 675 ms 116160 KB Output is correct
13 Correct 581 ms 116136 KB Output is correct
14 Correct 3 ms 3276 KB Output is correct
15 Correct 130 ms 116052 KB Output is correct
16 Correct 193 ms 116100 KB Output is correct
17 Correct 134 ms 116104 KB Output is correct
18 Correct 128 ms 116068 KB Output is correct
19 Correct 301 ms 116044 KB Output is correct
20 Correct 199 ms 116036 KB Output is correct
21 Correct 222 ms 116084 KB Output is correct
22 Correct 357 ms 116044 KB Output is correct
23 Correct 338 ms 116024 KB Output is correct
24 Correct 383 ms 116028 KB Output is correct
25 Correct 101 ms 115336 KB Output is correct
26 Correct 211 ms 116132 KB Output is correct
27 Correct 136 ms 116052 KB Output is correct
28 Correct 134 ms 116160 KB Output is correct
29 Correct 224 ms 116108 KB Output is correct
30 Correct 244 ms 116024 KB Output is correct
31 Correct 238 ms 116032 KB Output is correct
32 Correct 356 ms 116020 KB Output is correct
33 Correct 780 ms 116028 KB Output is correct
34 Correct 1223 ms 116040 KB Output is correct
35 Correct 793 ms 116020 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3276 KB Output is correct
2 Correct 810 ms 915288 KB Output is correct
3 Correct 763 ms 915276 KB Output is correct
4 Correct 847 ms 915372 KB Output is correct
5 Correct 835 ms 915436 KB Output is correct
6 Correct 1082 ms 915464 KB Output is correct
7 Correct 965 ms 915388 KB Output is correct
8 Correct 3 ms 3276 KB Output is correct
9 Correct 214 ms 116136 KB Output is correct
10 Correct 184 ms 116036 KB Output is correct
11 Correct 125 ms 116064 KB Output is correct
12 Correct 146 ms 116016 KB Output is correct
13 Correct 315 ms 116068 KB Output is correct
14 Correct 293 ms 116036 KB Output is correct
15 Correct 219 ms 116020 KB Output is correct
16 Correct 148 ms 116032 KB Output is correct
17 Correct 239 ms 116020 KB Output is correct
18 Correct 339 ms 116128 KB Output is correct
19 Correct 675 ms 116160 KB Output is correct
20 Correct 581 ms 116136 KB Output is correct
21 Correct 3 ms 3276 KB Output is correct
22 Correct 130 ms 116052 KB Output is correct
23 Correct 193 ms 116100 KB Output is correct
24 Correct 134 ms 116104 KB Output is correct
25 Correct 128 ms 116068 KB Output is correct
26 Correct 301 ms 116044 KB Output is correct
27 Correct 199 ms 116036 KB Output is correct
28 Correct 222 ms 116084 KB Output is correct
29 Correct 357 ms 116044 KB Output is correct
30 Correct 338 ms 116024 KB Output is correct
31 Correct 383 ms 116028 KB Output is correct
32 Correct 101 ms 115336 KB Output is correct
33 Correct 211 ms 116132 KB Output is correct
34 Correct 136 ms 116052 KB Output is correct
35 Correct 134 ms 116160 KB Output is correct
36 Correct 224 ms 116108 KB Output is correct
37 Correct 244 ms 116024 KB Output is correct
38 Correct 238 ms 116032 KB Output is correct
39 Correct 356 ms 116020 KB Output is correct
40 Correct 780 ms 116028 KB Output is correct
41 Correct 1223 ms 116040 KB Output is correct
42 Correct 793 ms 116020 KB Output is correct
43 Correct 1 ms 972 KB Output is correct
44 Correct 3 ms 3276 KB Output is correct
45 Correct 1122 ms 915408 KB Output is correct
46 Correct 852 ms 915516 KB Output is correct
47 Correct 857 ms 915288 KB Output is correct
48 Correct 897 ms 915412 KB Output is correct
49 Correct 1196 ms 915396 KB Output is correct
50 Correct 898 ms 915384 KB Output is correct
51 Correct 799 ms 915272 KB Output is correct
52 Correct 1016 ms 915388 KB Output is correct
53 Correct 1702 ms 915388 KB Output is correct
54 Correct 1771 ms 915512 KB Output is correct
55 Correct 2193 ms 915372 KB Output is correct
56 Correct 2322 ms 915396 KB Output is correct
57 Correct 2472 ms 915368 KB Output is correct
58 Correct 2518 ms 915364 KB Output is correct
59 Correct 2472 ms 915408 KB Output is correct
60 Correct 2311 ms 915292 KB Output is correct
61 Correct 2397 ms 915412 KB Output is correct