oj.uz

Submission #1050229

# Submission time Handle Problem Language Result Execution time Memory
1050229 2024-08-09T08:06:19 Z vjudge1 Dungeons Game (IOI21_dungeons) C++17
37 / 100
 1409 ms 1903592 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[400100][20];
	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<20;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[400100],p[400100],s[400100],w[400100],fin;
long long pws[20];
int llog(int x){
	for(int i=0;i<20;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<20;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));
		if(susss[K].thres(x,19)>z)
			return z+susss[K].strength(x,19);
		for(int i=19;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 490 ms 1881424 KB Output is correct
2 Correct 475 ms 1881428 KB Output is correct
3 Correct 494 ms 1881464 KB Output is correct
4 Correct 612 ms 1884680 KB Output is correct
5 Correct 495 ms 1881528 KB Output is correct
6 Correct 580 ms 1884444 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 1881440 KB Output is correct
2 Correct 1409 ms 1903592 KB Output is correct
3 Correct 1328 ms 1902816 KB Output is correct
4 Correct 1313 ms 1903396 KB Output is correct
5 Correct 1312 ms 1903364 KB Output is correct
6 Correct 1384 ms 1902824 KB Output is correct
7 Correct 1311 ms 1901908 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 1881568 KB Output is correct
2 Correct 597 ms 1885760 KB Output is correct
3 Correct 587 ms 1885932 KB Output is correct
4 Correct 558 ms 1885616 KB Output is correct
5 Correct 573 ms 1885524 KB Output is correct
6 Correct 590 ms 1885556 KB Output is correct
7 Incorrect 599 ms 1885520 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 1881568 KB Output is correct
2 Correct 597 ms 1885760 KB Output is correct
3 Correct 587 ms 1885932 KB Output is correct
4 Correct 558 ms 1885616 KB Output is correct
5 Correct 573 ms 1885524 KB Output is correct
6 Correct 590 ms 1885556 KB Output is correct
7 Incorrect 599 ms 1885520 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 1881568 KB Output is correct
2 Correct 597 ms 1885760 KB Output is correct
3 Correct 587 ms 1885932 KB Output is correct
4 Correct 558 ms 1885616 KB Output is correct
5 Correct 573 ms 1885524 KB Output is correct
6 Correct 590 ms 1885556 KB Output is correct
7 Incorrect 599 ms 1885520 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 1881440 KB Output is correct
2 Correct 1409 ms 1903592 KB Output is correct
3 Correct 1328 ms 1902816 KB Output is correct
4 Correct 1313 ms 1903396 KB Output is correct
5 Correct 1312 ms 1903364 KB Output is correct
6 Correct 1384 ms 1902824 KB Output is correct
7 Correct 1311 ms 1901908 KB Output is correct
8 Correct 503 ms 1881568 KB Output is correct
9 Correct 597 ms 1885760 KB Output is correct
10 Correct 587 ms 1885932 KB Output is correct
11 Correct 558 ms 1885616 KB Output is correct
12 Correct 573 ms 1885524 KB Output is correct
13 Correct 590 ms 1885556 KB Output is correct
14 Incorrect 599 ms 1885520 KB Output isn't correct
15 Halted 0 ms 0 KB -