oj.uz

Submission #1050246

# Submission time Handle Problem Language Result Execution time Memory
1050246 2024-08-09T08:13:13 Z vjudge1 Dungeons Game (IOI21_dungeons) C++17
50 / 100
 1690 ms 1904384 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));
		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 479 ms 1881304 KB Output is correct
2 Correct 505 ms 1881320 KB Output is correct
3 Correct 488 ms 1881536 KB Output is correct
4 Correct 573 ms 1884556 KB Output is correct
5 Correct 478 ms 1881684 KB Output is correct
6 Correct 540 ms 1884500 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 1881384 KB Output is correct
2 Correct 1380 ms 1903924 KB Output is correct
3 Correct 1319 ms 1904208 KB Output is correct
4 Correct 1343 ms 1904384 KB Output is correct
5 Correct 1321 ms 1904052 KB Output is correct
6 Correct 1378 ms 1903156 KB Output is correct
7 Correct 1319 ms 1902756 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 1881568 KB Output is correct
2 Correct 616 ms 1886060 KB Output is correct
3 Correct 578 ms 1886236 KB Output is correct
4 Correct 568 ms 1885520 KB Output is correct
5 Correct 563 ms 1885380 KB Output is correct
6 Correct 599 ms 1885764 KB Output is correct
7 Correct 628 ms 1885652 KB Output is correct
8 Correct 566 ms 1885260 KB Output is correct
9 Correct 566 ms 1885436 KB Output is correct
10 Correct 585 ms 1885252 KB Output is correct
11 Correct 578 ms 1885520 KB Output is correct
12 Correct 1690 ms 1885744 KB Output is correct
13 Correct 1564 ms 1885524 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 1881568 KB Output is correct
2 Correct 616 ms 1886060 KB Output is correct
3 Correct 578 ms 1886236 KB Output is correct
4 Correct 568 ms 1885520 KB Output is correct
5 Correct 563 ms 1885380 KB Output is correct
6 Correct 599 ms 1885764 KB Output is correct
7 Correct 628 ms 1885652 KB Output is correct
8 Correct 566 ms 1885260 KB Output is correct
9 Correct 566 ms 1885436 KB Output is correct
10 Correct 585 ms 1885252 KB Output is correct
11 Correct 578 ms 1885520 KB Output is correct
12 Correct 1690 ms 1885744 KB Output is correct
13 Correct 1564 ms 1885524 KB Output is correct
14 Correct 481 ms 1881552 KB Output is correct
15 Correct 573 ms 1885888 KB Output is correct
16 Correct 587 ms 1886148 KB Output is correct
17 Correct 617 ms 1885508 KB Output is correct
18 Correct 570 ms 1885648 KB Output is correct
19 Incorrect 583 ms 1885660 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 1881568 KB Output is correct
2 Correct 616 ms 1886060 KB Output is correct
3 Correct 578 ms 1886236 KB Output is correct
4 Correct 568 ms 1885520 KB Output is correct
5 Correct 563 ms 1885380 KB Output is correct
6 Correct 599 ms 1885764 KB Output is correct
7 Correct 628 ms 1885652 KB Output is correct
8 Correct 566 ms 1885260 KB Output is correct
9 Correct 566 ms 1885436 KB Output is correct
10 Correct 585 ms 1885252 KB Output is correct
11 Correct 578 ms 1885520 KB Output is correct
12 Correct 1690 ms 1885744 KB Output is correct
13 Correct 1564 ms 1885524 KB Output is correct
14 Correct 481 ms 1881552 KB Output is correct
15 Correct 573 ms 1885888 KB Output is correct
16 Correct 587 ms 1886148 KB Output is correct
17 Correct 617 ms 1885508 KB Output is correct
18 Correct 570 ms 1885648 KB Output is correct
19 Incorrect 583 ms 1885660 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 1881384 KB Output is correct
2 Correct 1380 ms 1903924 KB Output is correct
3 Correct 1319 ms 1904208 KB Output is correct
4 Correct 1343 ms 1904384 KB Output is correct
5 Correct 1321 ms 1904052 KB Output is correct
6 Correct 1378 ms 1903156 KB Output is correct
7 Correct 1319 ms 1902756 KB Output is correct
8 Correct 508 ms 1881568 KB Output is correct
9 Correct 616 ms 1886060 KB Output is correct
10 Correct 578 ms 1886236 KB Output is correct
11 Correct 568 ms 1885520 KB Output is correct
12 Correct 563 ms 1885380 KB Output is correct
13 Correct 599 ms 1885764 KB Output is correct
14 Correct 628 ms 1885652 KB Output is correct
15 Correct 566 ms 1885260 KB Output is correct
16 Correct 566 ms 1885436 KB Output is correct
17 Correct 585 ms 1885252 KB Output is correct
18 Correct 578 ms 1885520 KB Output is correct
19 Correct 1690 ms 1885744 KB Output is correct
20 Correct 1564 ms 1885524 KB Output is correct
21 Correct 481 ms 1881552 KB Output is correct
22 Correct 573 ms 1885888 KB Output is correct
23 Correct 587 ms 1886148 KB Output is correct
24 Correct 617 ms 1885508 KB Output is correct
25 Correct 570 ms 1885648 KB Output is correct
26 Incorrect 583 ms 1885660 KB Output isn't correct
27 Halted 0 ms 0 KB -