oj.uz

Submission #744543

# Submission time Handle Problem Language Result Execution time Memory
744543 2023-05-18T17:39:44 Z myrcella Dungeons Game (IOI21_dungeons) C++17
25 / 100
 659 ms 1094984 KB 
//by szh
#include<bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
 
#include "dungeons.h"
 
const int maxn = 4e5+10;
 
int nn;
ll ss[maxn],pp[maxn],ww[maxn],lr[maxn];
vector <int> val;
ll ans[maxn];
int st[5][24][maxn];
ll gain[5][24][maxn];
 
void gen(int id,int x) {
	rep(i,0,nn) st[id][0][i] = x>=ss[i]?ww[i]:lr[i], gain[id][0][i] = x>=ss[i]?ss[i]:pp[i];
	rep(i,1,24) rep(j,0,nn) {
		if (st[id][i-1][j]==-1) continue;
		st[id][i][j] = st[id][i-1][st[id][i-1][j]];
		gain[id][i][j] = gain[id][i-1][j] + gain[id][i-1][st[id][i-1][j]];
	}
}
 
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	memset(st,-1,sizeof(st));
	memset(gain,inf,sizeof(gain));
	nn = N;
	rep(i,0,nn) ss[i] = S[i], pp[i] = P[i], ww[i] = W[i], lr[i] = L[i],val.pb(ss[i]);
	sort(ALL(val));
	val.erase(unique(ALL(val)),val.end());reverse(ALL(val));
	ans[nn] = 0;
	for (int i=nn-1;i>=0;i--) ans[i] = ss[i] + ans[ww[i]];
	int hi = 0;
	for (int i = SZ(val)-1;i>=0;i--) gen(i,hi),hi = val[i];
	return;
}
 
long long simulate(int x, int z) {
	vector <int> valcur = val;
	
	ll ret = z;
	while (!valcur.empty()) {
		while (!valcur.empty() and ret >= valcur.back()) valcur.pop_back();
		if (valcur.empty()) break;
		int goal = valcur.back();
		int id = SZ(valcur)-1;
		for (int i=23;i>=0;i--) if (ret + gain[id][i][x] < goal) {
			ret += gain[id][i][x];
			x = st[id][i][x];
		}
		//debug(ret),debug(x);
		//check whether next step alrd reach goal
		if (x==nn) return ret;
		
		ll rett = ret;
		if (ret >= ss[x]) rett = ret + ss[x];
		else rett = ret + pp[x];
		x = ret>=ss[x]? ww[x]:lr[x];
		ret = rett;
		assert(ret>=goal);
		valcur.pop_back();
//		debug(ret);debug(x);
	}
//	debug(ans[x]);
	ret += ans[x];
	return ret;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 563876 KB Output is correct
2 Runtime error 612 ms 1080080 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 641 ms 1088532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 564040 KB Output is correct
2 Correct 243 ms 569188 KB Output is correct
3 Correct 252 ms 569200 KB Output is correct
4 Correct 248 ms 569196 KB Output is correct
5 Correct 239 ms 569200 KB Output is correct
6 Correct 263 ms 569240 KB Output is correct
7 Correct 278 ms 569928 KB Output is correct
8 Correct 267 ms 569628 KB Output is correct
9 Correct 243 ms 569572 KB Output is correct
10 Correct 242 ms 569452 KB Output is correct
11 Correct 297 ms 569744 KB Output is correct
12 Correct 294 ms 569876 KB Output is correct
13 Correct 283 ms 569828 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 564040 KB Output is correct
2 Correct 243 ms 569188 KB Output is correct
3 Correct 252 ms 569200 KB Output is correct
4 Correct 248 ms 569196 KB Output is correct
5 Correct 239 ms 569200 KB Output is correct
6 Correct 263 ms 569240 KB Output is correct
7 Correct 278 ms 569928 KB Output is correct
8 Correct 267 ms 569628 KB Output is correct
9 Correct 243 ms 569572 KB Output is correct
10 Correct 242 ms 569452 KB Output is correct
11 Correct 297 ms 569744 KB Output is correct
12 Correct 294 ms 569876 KB Output is correct
13 Correct 283 ms 569828 KB Output is correct
14 Correct 229 ms 563972 KB Output is correct
15 Correct 291 ms 570016 KB Output is correct
16 Correct 267 ms 570192 KB Output is correct
17 Correct 268 ms 569692 KB Output is correct
18 Correct 284 ms 569820 KB Output is correct
19 Correct 311 ms 569860 KB Output is correct
20 Correct 295 ms 569484 KB Output is correct
21 Correct 306 ms 569716 KB Output is correct
22 Correct 277 ms 569680 KB Output is correct
23 Correct 297 ms 569800 KB Output is correct
24 Correct 387 ms 569796 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 564040 KB Output is correct
2 Correct 243 ms 569188 KB Output is correct
3 Correct 252 ms 569200 KB Output is correct
4 Correct 248 ms 569196 KB Output is correct
5 Correct 239 ms 569200 KB Output is correct
6 Correct 263 ms 569240 KB Output is correct
7 Correct 278 ms 569928 KB Output is correct
8 Correct 267 ms 569628 KB Output is correct
9 Correct 243 ms 569572 KB Output is correct
10 Correct 242 ms 569452 KB Output is correct
11 Correct 297 ms 569744 KB Output is correct
12 Correct 294 ms 569876 KB Output is correct
13 Correct 283 ms 569828 KB Output is correct
14 Correct 229 ms 563972 KB Output is correct
15 Correct 291 ms 570016 KB Output is correct
16 Correct 267 ms 570192 KB Output is correct
17 Correct 268 ms 569692 KB Output is correct
18 Correct 284 ms 569820 KB Output is correct
19 Correct 311 ms 569860 KB Output is correct
20 Correct 295 ms 569484 KB Output is correct
21 Correct 306 ms 569716 KB Output is correct
22 Correct 277 ms 569680 KB Output is correct
23 Correct 297 ms 569800 KB Output is correct
24 Correct 387 ms 569796 KB Output is correct
25 Runtime error 659 ms 1094984 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 641 ms 1088532 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -