oj.uz

Submission #437869

# Submission time Handle Problem Language Result Execution time Memory
437869 2021-06-27T08:30:59 Z b00n0rp Dungeons Game (IOI21_dungeons) C++17
63 / 100
 2726 ms 1048580 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
 
#define int long long
 
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
 
const int MX = 400005;
const int LG = 25;
const int STA = 5;
 
int n,s[MX],p[MX],w[MX],l[MX];
pii win[MX][LG+5];
int wincond[MX][LG+1];
pii lose[STA+1][MX][LG+1]; 
int losecond[STA+1][MX][LG+1];
vi st;
 
void init(signed n0, vector<signed> s0, vector<signed> p0, vector<signed> w0, vector<signed> l0) {
	n = n0;
	REP(i,n){
		s[i] = s0[i];
		p[i] = p0[i];
		w[i] = w0[i];
		l[i] = l0[i];
	}
	st.pb(4);
	FOR(i,1,STA) st.pb(4*st.back());
	w[n] = n;
	l[n] = n;
	s[n] = 0;
	p[n] = 0;
	REP(i,n+1){
		win[i][0] = {w[i],s[i]};
		wincond[i][0] = s[w[i]]-s[i];
	}
	FOR(j,1,LG+1){
		REP(i,n+1){
			win[i][j] = {win[win[i][j-1].F][j-1].F,win[win[i][j-1].F][j-1].S+win[i][j-1].S};
			wincond[i][j] = max(wincond[i][j-1],wincond[win[i][j-1].F][j-1]-win[i][j-1].S);
		}
	}
	REP(stage,STA+1){
		REP(i,n){
			if(stage and s[i] <= st[stage-1]){
				l[i] = w[i];
				p[i] = s[i];
				s[i] = (int)1e16;
			}
		}
		REP(i,n+1){
			lose[stage][i][0] = {l[i],p[i]};
			losecond[stage][i][0] = s[l[i]]-p[i];
			// int j = 0;
			// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
		}
		FOR(j,1,LG+1){
			REP(i,n+1){
				lose[stage][i][j] = {lose[stage][lose[stage][i][j-1].F][j-1].F,lose[stage][lose[stage][i][j-1].F][j-1].S+lose[stage][i][j-1].S};
				losecond[stage][i][j] = min(losecond[stage][i][j-1],losecond[stage][lose[stage][i][j-1].F][j-1]-lose[stage][i][j-1].S);
				// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
			}
		}
		REP(i,n){
			s[i] = s0[i];
			p[i] = p0[i];
			w[i] = w0[i];
			l[i] = l0[i];
		}
	}
}
 
int simulate(signed x, signed z) {
	int ind = x;
	int ans = z;
	int stage = 0;
	while(ind != n){
		// cout << ind << " " << ans << "\n";
		if(s[ind] > ans){
			while(stage < STA and st[stage] <= ans) stage++;
			for(int j = LG; j >= 0; j --){
				if(losecond[stage][ind][j] > ans){
					ans += lose[stage][ind][j].S;
					ind = lose[stage][ind][j].F;
				}
			}
			if(s[ind] > ans){
				ans += p[ind];
				ind = l[ind];
			}
		}
		else{
			for(int j = LG; j >= 0; j --){
				if(wincond[ind][j] <= ans){
					ans += win[ind][j].S;
					ind = win[ind][j].F;
				}
			}
			ans += s[ind];
			ind = w[ind];
		}
	}
	return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 9 ms 9164 KB Output is correct
4 Correct 403 ms 220312 KB Output is correct
5 Correct 8 ms 9164 KB Output is correct
6 Correct 415 ms 221232 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4812 KB Output is correct
2 Runtime error 2222 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4812 KB Output is correct
2 Correct 450 ms 221196 KB Output is correct
3 Correct 426 ms 221136 KB Output is correct
4 Correct 439 ms 221280 KB Output is correct
5 Correct 442 ms 221268 KB Output is correct
6 Correct 513 ms 221168 KB Output is correct
7 Correct 534 ms 221196 KB Output is correct
8 Correct 516 ms 221160 KB Output is correct
9 Correct 477 ms 221224 KB Output is correct
10 Correct 436 ms 221128 KB Output is correct
11 Correct 607 ms 221252 KB Output is correct
12 Correct 709 ms 221252 KB Output is correct
13 Correct 631 ms 221252 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4812 KB Output is correct
2 Correct 450 ms 221196 KB Output is correct
3 Correct 426 ms 221136 KB Output is correct
4 Correct 439 ms 221280 KB Output is correct
5 Correct 442 ms 221268 KB Output is correct
6 Correct 513 ms 221168 KB Output is correct
7 Correct 534 ms 221196 KB Output is correct
8 Correct 516 ms 221160 KB Output is correct
9 Correct 477 ms 221224 KB Output is correct
10 Correct 436 ms 221128 KB Output is correct
11 Correct 607 ms 221252 KB Output is correct
12 Correct 709 ms 221252 KB Output is correct
13 Correct 631 ms 221252 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 460 ms 221136 KB Output is correct
16 Correct 454 ms 221124 KB Output is correct
17 Correct 481 ms 221124 KB Output is correct
18 Correct 440 ms 221252 KB Output is correct
19 Correct 483 ms 221252 KB Output is correct
20 Correct 472 ms 221252 KB Output is correct
21 Correct 483 ms 221132 KB Output is correct
22 Correct 530 ms 221252 KB Output is correct
23 Correct 558 ms 221208 KB Output is correct
24 Correct 711 ms 221136 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4812 KB Output is correct
2 Correct 450 ms 221196 KB Output is correct
3 Correct 426 ms 221136 KB Output is correct
4 Correct 439 ms 221280 KB Output is correct
5 Correct 442 ms 221268 KB Output is correct
6 Correct 513 ms 221168 KB Output is correct
7 Correct 534 ms 221196 KB Output is correct
8 Correct 516 ms 221160 KB Output is correct
9 Correct 477 ms 221224 KB Output is correct
10 Correct 436 ms 221128 KB Output is correct
11 Correct 607 ms 221252 KB Output is correct
12 Correct 709 ms 221252 KB Output is correct
13 Correct 631 ms 221252 KB Output is correct
14 Correct 6 ms 4992 KB Output is correct
15 Correct 460 ms 221136 KB Output is correct
16 Correct 454 ms 221124 KB Output is correct
17 Correct 481 ms 221124 KB Output is correct
18 Correct 440 ms 221252 KB Output is correct
19 Correct 483 ms 221252 KB Output is correct
20 Correct 472 ms 221252 KB Output is correct
21 Correct 483 ms 221132 KB Output is correct
22 Correct 530 ms 221252 KB Output is correct
23 Correct 558 ms 221208 KB Output is correct
24 Correct 711 ms 221136 KB Output is correct
25 Correct 391 ms 220368 KB Output is correct
26 Correct 435 ms 221124 KB Output is correct
27 Correct 482 ms 221380 KB Output is correct
28 Correct 455 ms 221192 KB Output is correct
29 Correct 457 ms 221268 KB Output is correct
30 Correct 493 ms 221280 KB Output is correct
31 Correct 487 ms 221192 KB Output is correct
32 Correct 713 ms 221204 KB Output is correct
33 Correct 1343 ms 221064 KB Output is correct
34 Correct 1584 ms 221008 KB Output is correct
35 Correct 2726 ms 221124 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4812 KB Output is correct
2 Runtime error 2222 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -