oj.uz

Submission #1052804

# Submission time Handle Problem Language Result Execution time Memory
1052804 2024-08-10T23:15:13 Z Edu175 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4787 ms 1760032 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b; i<ioi; i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto kdfhg:v)cout<<kdfhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll K=8,VK=25,MAXN=4e5+5,INF=1e18,B=8;
ll n;
ll s[MAXN],p[MAXN],w[MAXN],l[MAXN];

ii oper(ii a, ii b){
	return {min((ll)a.fst,b.fst-a.snd),min(a.snd+b.snd,INF)};
}
struct bloque{
	ll pot;
	ll a[MAXN],v[MAXN];
	int F[K][MAXN];
	ii V[K][MAXN];
	void init(ll _pot){
		pot=_pot;
		fore(i,0,n){
			if(pot<s[i]){
				a[i]=l[i];
				v[i]=p[i];
			}
			else {
				a[i]=w[i];
				v[i]=s[i];
			}
		}
		fore(i,0,n){
			F[0][i]=a[i];
			V[0][i]={(pot<s[i]?s[i]:INF),v[i]};
			// if(a[i]==n)V[0][i].fst=-1;
		}
		F[0][n]=n;
		V[0][n]={-1,0};
		fore(k,1,K)fore(i,0,n+1){
			auto &x=F[k][i];
			x=i;
			V[k][i]={INF,0};
			fore(j,0,B){
				V[k][i]=oper(V[k][i],V[k-1][x]);
				x=F[k-1][x];
			}
		}
		// cout<<"bloque "<<pot<<":\n";
		// fore(i,0,n)cout<<a[i]<<" ";;cout<<"\n";
		// fore(i,0,n)cout<<v[i]<<" ";;cout<<"\n";
		// fore(i,0,n)cout<<V[0][i].fst<<","<<V[0][i].snd<<" ";;cout<<"\n";
	}
	void go(ll &x, ll &z){
		// cout<<"go "<<x<<" "<<z<<endl;
		assert(z<INF);
		for(ll k=K-1;k>=0;k--)fore(j,0,B){
			auto nod=V[k][x];
			if(z<nod.fst&&F[k][x]<n){
				z+=nod.snd;
				// cout<<"salto "<<k<<"\n";
				// cout<<x<<" -> "<<F[k][x]<<"\n";
				// cout<<nod.fst<<","<<nod.snd<<"\n";
				assert(z<INF);
				x=F[k][x];
			}
			else break;
		}
		// nod=oper(nod,V[0][x]);
		// cout<<"salto final"<<"\n";
		// cout<<x<<" -> "<<F[0][x]<<"\n";
		// cout<<nod.fst<<","<<nod.snd<<"\n";
		// x=F[0][x];
		// z+=nod.snd;
		// cout<<"ended in "<<x<<","<<z<<endl;
		// assert((pot<s[x]&&z>=s[x]));
		if((pot>=s[x]||z<s[x])&&a[x]==n){
			z+=v[x]; x=a[x];
			assert(x==n);
		}
		else {
			// assert(pot<s[x]&&z>=s[x]);
			z+=s[x]; x=w[x];
		}
		// cout<<x<<" "<<z<<"\n\n";
	}
};
bloque dat[VK];
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
	n=N;
	fore(i,0,n){
		s[i]=S[i];
		p[i]=P[i];
		w[i]=W[i];
		l[i]=L[i];
	}
	fore(i,0,VK)dat[i].init(1ll<<i);
}
long long simulate(int X, int Z){
	ll x=X,z=Z;
	while(x<n){
		ll bl=min(VK-1,ll(63-__builtin_clzll(z)));
		dat[bl].go(x,z);
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 1271636 KB Output is correct
2 Correct 333 ms 1271632 KB Output is correct
3 Correct 336 ms 1273940 KB Output is correct
4 Correct 512 ms 1331004 KB Output is correct
5 Correct 334 ms 1274056 KB Output is correct
6 Correct 515 ms 1331028 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 1272912 KB Output is correct
2 Correct 1765 ms 1755300 KB Output is correct
3 Correct 1660 ms 1755232 KB Output is correct
4 Correct 1720 ms 1756836 KB Output is correct
5 Correct 1890 ms 1756836 KB Output is correct
6 Correct 1777 ms 1755124 KB Output is correct
7 Correct 1698 ms 1753276 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 1272912 KB Output is correct
2 Correct 560 ms 1332572 KB Output is correct
3 Correct 534 ms 1332544 KB Output is correct
4 Correct 513 ms 1332016 KB Output is correct
5 Correct 510 ms 1331792 KB Output is correct
6 Correct 583 ms 1332216 KB Output is correct
7 Correct 578 ms 1332052 KB Output is correct
8 Correct 523 ms 1331936 KB Output is correct
9 Correct 542 ms 1331880 KB Output is correct
10 Correct 529 ms 1331756 KB Output is correct
11 Correct 629 ms 1332052 KB Output is correct
12 Correct 738 ms 1332216 KB Output is correct
13 Correct 565 ms 1332308 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 1272912 KB Output is correct
2 Correct 560 ms 1332572 KB Output is correct
3 Correct 534 ms 1332544 KB Output is correct
4 Correct 513 ms 1332016 KB Output is correct
5 Correct 510 ms 1331792 KB Output is correct
6 Correct 583 ms 1332216 KB Output is correct
7 Correct 578 ms 1332052 KB Output is correct
8 Correct 523 ms 1331936 KB Output is correct
9 Correct 542 ms 1331880 KB Output is correct
10 Correct 529 ms 1331756 KB Output is correct
11 Correct 629 ms 1332052 KB Output is correct
12 Correct 738 ms 1332216 KB Output is correct
13 Correct 565 ms 1332308 KB Output is correct
14 Correct 348 ms 1272912 KB Output is correct
15 Correct 529 ms 1332212 KB Output is correct
16 Correct 564 ms 1332548 KB Output is correct
17 Correct 513 ms 1332036 KB Output is correct
18 Correct 520 ms 1332052 KB Output is correct
19 Correct 590 ms 1332036 KB Output is correct
20 Correct 537 ms 1331792 KB Output is correct
21 Correct 529 ms 1332048 KB Output is correct
22 Correct 523 ms 1332256 KB Output is correct
23 Correct 637 ms 1332012 KB Output is correct
24 Correct 703 ms 1332052 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 1272912 KB Output is correct
2 Correct 560 ms 1332572 KB Output is correct
3 Correct 534 ms 1332544 KB Output is correct
4 Correct 513 ms 1332016 KB Output is correct
5 Correct 510 ms 1331792 KB Output is correct
6 Correct 583 ms 1332216 KB Output is correct
7 Correct 578 ms 1332052 KB Output is correct
8 Correct 523 ms 1331936 KB Output is correct
9 Correct 542 ms 1331880 KB Output is correct
10 Correct 529 ms 1331756 KB Output is correct
11 Correct 629 ms 1332052 KB Output is correct
12 Correct 738 ms 1332216 KB Output is correct
13 Correct 565 ms 1332308 KB Output is correct
14 Correct 348 ms 1272912 KB Output is correct
15 Correct 529 ms 1332212 KB Output is correct
16 Correct 564 ms 1332548 KB Output is correct
17 Correct 513 ms 1332036 KB Output is correct
18 Correct 520 ms 1332052 KB Output is correct
19 Correct 590 ms 1332036 KB Output is correct
20 Correct 537 ms 1331792 KB Output is correct
21 Correct 529 ms 1332048 KB Output is correct
22 Correct 523 ms 1332256 KB Output is correct
23 Correct 637 ms 1332012 KB Output is correct
24 Correct 703 ms 1332052 KB Output is correct
25 Correct 561 ms 1331368 KB Output is correct
26 Correct 568 ms 1332724 KB Output is correct
27 Correct 546 ms 1332032 KB Output is correct
28 Correct 535 ms 1332036 KB Output is correct
29 Correct 565 ms 1332480 KB Output is correct
30 Correct 539 ms 1332048 KB Output is correct
31 Correct 536 ms 1331796 KB Output is correct
32 Correct 733 ms 1332056 KB Output is correct
33 Correct 596 ms 1332052 KB Output is correct
34 Correct 924 ms 1331932 KB Output is correct
35 Correct 642 ms 1331840 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 1272912 KB Output is correct
2 Correct 1765 ms 1755300 KB Output is correct
3 Correct 1660 ms 1755232 KB Output is correct
4 Correct 1720 ms 1756836 KB Output is correct
5 Correct 1890 ms 1756836 KB Output is correct
6 Correct 1777 ms 1755124 KB Output is correct
7 Correct 1698 ms 1753276 KB Output is correct
8 Correct 338 ms 1272912 KB Output is correct
9 Correct 560 ms 1332572 KB Output is correct
10 Correct 534 ms 1332544 KB Output is correct
11 Correct 513 ms 1332016 KB Output is correct
12 Correct 510 ms 1331792 KB Output is correct
13 Correct 583 ms 1332216 KB Output is correct
14 Correct 578 ms 1332052 KB Output is correct
15 Correct 523 ms 1331936 KB Output is correct
16 Correct 542 ms 1331880 KB Output is correct
17 Correct 529 ms 1331756 KB Output is correct
18 Correct 629 ms 1332052 KB Output is correct
19 Correct 738 ms 1332216 KB Output is correct
20 Correct 565 ms 1332308 KB Output is correct
21 Correct 348 ms 1272912 KB Output is correct
22 Correct 529 ms 1332212 KB Output is correct
23 Correct 564 ms 1332548 KB Output is correct
24 Correct 513 ms 1332036 KB Output is correct
25 Correct 520 ms 1332052 KB Output is correct
26 Correct 590 ms 1332036 KB Output is correct
27 Correct 537 ms 1331792 KB Output is correct
28 Correct 529 ms 1332048 KB Output is correct
29 Correct 523 ms 1332256 KB Output is correct
30 Correct 637 ms 1332012 KB Output is correct
31 Correct 703 ms 1332052 KB Output is correct
32 Correct 561 ms 1331368 KB Output is correct
33 Correct 568 ms 1332724 KB Output is correct
34 Correct 546 ms 1332032 KB Output is correct
35 Correct 535 ms 1332036 KB Output is correct
36 Correct 565 ms 1332480 KB Output is correct
37 Correct 539 ms 1332048 KB Output is correct
38 Correct 536 ms 1331796 KB Output is correct
39 Correct 733 ms 1332056 KB Output is correct
40 Correct 596 ms 1332052 KB Output is correct
41 Correct 924 ms 1331932 KB Output is correct
42 Correct 642 ms 1331840 KB Output is correct
43 Correct 343 ms 1271636 KB Output is correct
44 Correct 347 ms 1272912 KB Output is correct
45 Correct 2902 ms 1760032 KB Output is correct
46 Correct 1988 ms 1755308 KB Output is correct
47 Correct 1960 ms 1755552 KB Output is correct
48 Correct 1849 ms 1757944 KB Output is correct
49 Correct 2961 ms 1759896 KB Output is correct
50 Correct 1703 ms 1757548 KB Output is correct
51 Correct 1832 ms 1757776 KB Output is correct
52 Correct 1674 ms 1755456 KB Output is correct
53 Correct 4058 ms 1756236 KB Output is correct
54 Correct 1891 ms 1757416 KB Output is correct
55 Correct 2879 ms 1756408 KB Output is correct
56 Correct 3358 ms 1757004 KB Output is correct
57 Correct 3325 ms 1757148 KB Output is correct
58 Correct 3443 ms 1756640 KB Output is correct
59 Correct 3653 ms 1755648 KB Output is correct
60 Correct 4787 ms 1752860 KB Output is correct
61 Correct 3204 ms 1748412 KB Output is correct