oj.uz

Submission #1051206

# Submission time Handle Problem Language Result Execution time Memory
1051206 2024-08-09T23:48:11 Z Edu175 Dungeons Game (IOI21_dungeons) C++17
11 / 100
 604 ms 1131088 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=30,VK=30,MAXN=5e4+5,INF=1e15;

ll n;
ll s[MAXN],p[MAXN],w[MAXN],l[MAXN];

ii oper(ii a, ii b){
	return {min(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(x,0,n+1){
			F[k][x]=F[k-1][F[k-1][x]];
			V[k][x]=oper(V[k-1][x],V[k-1][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);
		ii nod={INF,0};
		for(ll k=K-1;k>=0;k--){
			auto nodi=oper(nod,V[k][x]);
			if(z<nodi.fst&&F[k][x]<n){
				// nod=nodi;
				z+=nodi.snd;
				// cout<<"salto "<<k<<"\n";
				// cout<<x<<" -> "<<F[k][x]<<"\n";
				// cout<<nod.fst<<","<<nod.snd<<"\n";
				assert(z<INF);
				x=F[k][x];
			}
		}
		// 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]);
		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 229 ms 709040 KB Output is correct
2 Correct 213 ms 709212 KB Output is correct
3 Correct 218 ms 717152 KB Output is correct
4 Correct 390 ms 908136 KB Output is correct
5 Correct 226 ms 717148 KB Output is correct
6 Correct 400 ms 908540 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 713412 KB Output is correct
2 Runtime error 604 ms 1131088 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 233 ms 713568 KB Output is correct
2 Correct 392 ms 910196 KB Output is correct
3 Correct 416 ms 910388 KB Output is correct
4 Correct 371 ms 909664 KB Output is correct
5 Correct 406 ms 909400 KB Output is correct
6 Correct 420 ms 909920 KB Output is correct
7 Correct 411 ms 909656 KB Output is correct
8 Correct 412 ms 909408 KB Output is correct
9 Correct 386 ms 909408 KB Output is correct
10 Correct 390 ms 909392 KB Output is correct
11 Incorrect 410 ms 909848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 713568 KB Output is correct
2 Correct 392 ms 910196 KB Output is correct
3 Correct 416 ms 910388 KB Output is correct
4 Correct 371 ms 909664 KB Output is correct
5 Correct 406 ms 909400 KB Output is correct
6 Correct 420 ms 909920 KB Output is correct
7 Correct 411 ms 909656 KB Output is correct
8 Correct 412 ms 909408 KB Output is correct
9 Correct 386 ms 909408 KB Output is correct
10 Correct 390 ms 909392 KB Output is correct
11 Incorrect 410 ms 909848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 713568 KB Output is correct
2 Correct 392 ms 910196 KB Output is correct
3 Correct 416 ms 910388 KB Output is correct
4 Correct 371 ms 909664 KB Output is correct
5 Correct 406 ms 909400 KB Output is correct
6 Correct 420 ms 909920 KB Output is correct
7 Correct 411 ms 909656 KB Output is correct
8 Correct 412 ms 909408 KB Output is correct
9 Correct 386 ms 909408 KB Output is correct
10 Correct 390 ms 909392 KB Output is correct
11 Incorrect 410 ms 909848 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 713412 KB Output is correct
2 Runtime error 604 ms 1131088 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -