oj.uz

Submission #442901

# Submission time Handle Problem Language Result Execution time Memory
442901 2021-07-09T10:37:28 Z JvThunder Dungeons Game (IOI21_dungeons) C++17
11 / 100
 932 ms 616232 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define fir first
#define sec second
typedef long long ll;
using namespace std;

int N;
vector<int> S,P,W,L;
ll jump[11][22][50005]; // 8^b,2^jump,pos
ll add[11][22][50005];
ll need[11][22][50005]; //beat all

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;
	
	int tmp = 1;
	for(int bit=0;bit<=10;bit++)
	{
		int lim = tmp;
		
		for(int i=0;i<n;i++) 
		{
			if(s[i]<=lim) add[bit][0][i] = s[i], jump[bit][0][i] = w[i], need[bit][0][i] = s[i];
			else if(s[i]>8*lim) add[bit][0][i] = p[i], jump[bit][0][i] = l[i], need[bit][0][i] = 0;
			else add[bit][0][i] = 0, jump[bit][0][i] = i, need[bit][0][i] = 0;
		}
		need[bit][0][n] = 0, add[bit][0][n] = 0, jump[bit][0][n] = n;

		for(int i=1;i<=21;i++)
		{
			for(int j=0;j<=n;j++)
			{
				int nxt = jump[bit][i-1][j];
				add[bit][i][j] = add[bit][i-1][j] + add[bit][i-1][nxt];
				need[bit][i][j] = max(need[bit][i-1][j], need[bit][i-1][nxt]);
				jump[bit][i][j] = jump[bit][i-1][nxt];
			}
		}

		tmp *= 8;
	}
	return;
}

ll simulate(int x, int z) 
{
	ll pos = x;
	ll str = z;
	
	ll tmp = 1;
	ll phase = 0;
	while(pos!=N && phase<=10)
	{
		tmp *= 8;

		for(int i=21;i>=0;i--)
		{
			if(need[phase][i][pos]<=str && str+add[phase][i][pos]<=tmp && jump[phase][i][pos]!=N)
			{
				str += add[phase][i][pos]; 
				pos = jump[phase][i][pos]; 
			}
		}

		while(pos!=N && str<=tmp)
		{
			if(str>=S[pos]) str += S[pos], pos = W[pos];
			else str += P[pos], pos = L[pos];
		}

		phase++;
	}
	return str;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3660 KB Output is correct
2 Correct 2 ms 3788 KB Output is correct
3 Correct 11 ms 15180 KB Output is correct
4 Correct 209 ms 286784 KB Output is correct
5 Correct 10 ms 15196 KB Output is correct
6 Correct 198 ms 286804 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9420 KB Output is correct
2 Runtime error 921 ms 616232 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9420 KB Output is correct
2 Correct 798 ms 287552 KB Output is correct
3 Incorrect 932 ms 287492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9420 KB Output is correct
2 Correct 798 ms 287552 KB Output is correct
3 Incorrect 932 ms 287492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9420 KB Output is correct
2 Correct 798 ms 287552 KB Output is correct
3 Incorrect 932 ms 287492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9420 KB Output is correct
2 Runtime error 921 ms 616232 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -