oj.uz

Submission #1050252

# Submission time Handle Problem Language Result Execution time Memory
1050252 2024-08-09T08:16:40 Z vjudge1 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 575 ms 630416 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct level {
	private:
	struct dAtA{
		int to;
		long long inc,thres;
		dAtA(int go,int add,long long T){
			to=go,inc=add,thres=T;
		}
		dAtA(){
			to=0,inc=0,thres=0;
		}
		dAtA(dAtA a,dAtA b){
			to=b.to;
			inc=a.inc+b.inc;
			thres=min(1ll*a.thres,b.thres-a.inc);
		}
	} bj[50100][25];
	public:
	long long strength(int n,int k){
		return bj[n][k].inc;
	}
	long long thres(int n,int k){
		return bj[n][k].thres;
	}
	int dungeon(int n,int k){
		return bj[n][k].to;
	}
	void setdungeon(int n,int go,int add,long long T){
		bj[n][0]=dAtA(go,add,T);
	}
	void preproc(int n){
		for(int j=1;j<25;j++) for(int i=0;i<=n;i++)
			bj[i][j]=dAtA(bj[i][j-1],bj[bj[i][j-1].to][j-1]);
	}
} susss[10];
int l[50100],p[50100],s[50100],w[50100],fin;
long long pws[25];
int llog(int x){
	for(int i=0;i<25;i++)
		if(pws[i+1]>x)
			return i;
}
void init(int n,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
	fin=n;
	pws[0]=1;
	for(int i=1;i<25;i++)
		pws[i]=pws[i-1]*8;
	for(int i=0;i<n;i++) l[i]=L[i],p[i]=P[i],s[i]=S[i],w[i]=W[i];
	for(int j=0;j<10;j++)
		for(int i=0;i<n;i++) {
			if(s[i]<=pws[j])
				susss[j].setdungeon(i,w[i],s[i],1e18);
			else susss[j].setdungeon(i,l[i],p[i],s[i]);
		}
	for(int i=0;i<10;i++)
		susss[i].setdungeon(n,n,0,1e18),
		susss[i].preproc(n);
}

long long simulate(int x, int Z) {
	long long z=Z;
	while(1){
		int K=min(9,llog(z));
		for(int i=25;i--;)
			if(susss[K].thres(x,i)>z)
				z+=susss[K].strength(x,i),
				x=susss[K].dungeon(x,i);
		if(x==fin) return z;
		int k=s[x];
		if(k<=z)
			x=w[x],z+=k;
		else x=l[x],z+=p[x];
		if(x==fin) return z;
	}
}

Compilation message

dungeons.cpp: In function 'int llog(int)':
dungeons.cpp:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 294936 KB Output is correct
2 Correct 73 ms 294924 KB Output is correct
3 Correct 77 ms 295248 KB Output is correct
4 Correct 165 ms 297808 KB Output is correct
5 Correct 76 ms 295248 KB Output is correct
6 Correct 167 ms 297732 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 294992 KB Output is correct
2 Runtime error 413 ms 630416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 295156 KB Output is correct
2 Correct 188 ms 298636 KB Output is correct
3 Correct 182 ms 298832 KB Output is correct
4 Correct 165 ms 298540 KB Output is correct
5 Correct 203 ms 298208 KB Output is correct
6 Correct 191 ms 298320 KB Output is correct
7 Correct 182 ms 298248 KB Output is correct
8 Correct 162 ms 298320 KB Output is correct
9 Correct 169 ms 298200 KB Output is correct
10 Correct 181 ms 298072 KB Output is correct
11 Correct 164 ms 298320 KB Output is correct
12 Correct 216 ms 298320 KB Output is correct
13 Correct 200 ms 298324 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 295156 KB Output is correct
2 Correct 188 ms 298636 KB Output is correct
3 Correct 182 ms 298832 KB Output is correct
4 Correct 165 ms 298540 KB Output is correct
5 Correct 203 ms 298208 KB Output is correct
6 Correct 191 ms 298320 KB Output is correct
7 Correct 182 ms 298248 KB Output is correct
8 Correct 162 ms 298320 KB Output is correct
9 Correct 169 ms 298200 KB Output is correct
10 Correct 181 ms 298072 KB Output is correct
11 Correct 164 ms 298320 KB Output is correct
12 Correct 216 ms 298320 KB Output is correct
13 Correct 200 ms 298324 KB Output is correct
14 Correct 68 ms 294996 KB Output is correct
15 Correct 177 ms 297556 KB Output is correct
16 Correct 188 ms 297556 KB Output is correct
17 Correct 166 ms 297688 KB Output is correct
18 Correct 174 ms 297548 KB Output is correct
19 Correct 180 ms 297688 KB Output is correct
20 Correct 186 ms 298676 KB Output is correct
21 Correct 186 ms 298616 KB Output is correct
22 Correct 168 ms 298668 KB Output is correct
23 Correct 172 ms 298832 KB Output is correct
24 Correct 238 ms 298988 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 295156 KB Output is correct
2 Correct 188 ms 298636 KB Output is correct
3 Correct 182 ms 298832 KB Output is correct
4 Correct 165 ms 298540 KB Output is correct
5 Correct 203 ms 298208 KB Output is correct
6 Correct 191 ms 298320 KB Output is correct
7 Correct 182 ms 298248 KB Output is correct
8 Correct 162 ms 298320 KB Output is correct
9 Correct 169 ms 298200 KB Output is correct
10 Correct 181 ms 298072 KB Output is correct
11 Correct 164 ms 298320 KB Output is correct
12 Correct 216 ms 298320 KB Output is correct
13 Correct 200 ms 298324 KB Output is correct
14 Correct 68 ms 294996 KB Output is correct
15 Correct 177 ms 297556 KB Output is correct
16 Correct 188 ms 297556 KB Output is correct
17 Correct 166 ms 297688 KB Output is correct
18 Correct 174 ms 297548 KB Output is correct
19 Correct 180 ms 297688 KB Output is correct
20 Correct 186 ms 298676 KB Output is correct
21 Correct 186 ms 298616 KB Output is correct
22 Correct 168 ms 298668 KB Output is correct
23 Correct 172 ms 298832 KB Output is correct
24 Correct 238 ms 298988 KB Output is correct
25 Correct 152 ms 298128 KB Output is correct
26 Correct 179 ms 299328 KB Output is correct
27 Correct 166 ms 298576 KB Output is correct
28 Correct 165 ms 298820 KB Output is correct
29 Correct 189 ms 299088 KB Output is correct
30 Correct 190 ms 298844 KB Output is correct
31 Correct 193 ms 298588 KB Output is correct
32 Correct 205 ms 298668 KB Output is correct
33 Correct 262 ms 298832 KB Output is correct
34 Correct 575 ms 298580 KB Output is correct
35 Correct 250 ms 298828 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 294992 KB Output is correct
2 Runtime error 413 ms 630416 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -