oj.uz

Submission #921291

# Submission time Handle Problem Language Result Execution time Memory
921291 2024-02-03T16:24:57 Z byunjaewoo Dungeons Game (IOI21_dungeons) C++17
63 / 100
 4645 ms 2097152 KB 
#include "dungeons.h"
#pragma gcc optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=400001;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll DP[Nmax];
vector<int> nxt[24][Nmax], mx[24][Nmax], sum[24][Nmax];
 
void init(int n, std::vector<int> S_, std::vector<int> P_, std::vector<int> W_, std::vector<int> L_) {
	N=n;
	for(int i=0; i<N; i++) S[i]=S_[i], P[i]=P_[i], W[i]=W_[i], L[i]=L_[i];
	for(int i=0; i<24; i++) for(int j=0; j<=N; j++) nxt[i][j].resize(i), mx[i][j].resize(i), sum[i][j].resize(i);
	for(int i=1; i<24; i++) {
		for(int j=0; j<N; j++) {
			if(S[j]>=(1<<(i+1))) nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=(1<<(i+1))-1-P[j];
			else if(S[j]<=(1<<i)) nxt[i][j][0]=W[j], sum[i][j][0]=S[j], mx[i][j][0]=(1<<(i+1))-1-S[j];
			else nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=min(S[j]-1, (1<<(i+1))-1-P[j]);
		}
		nxt[i][N][0]=N, sum[i][N][0]=0, mx[i][N][0]=(1<<(i+1))-1;
		for(int j=1; j<i; j++) for(int k=0; k<=N; k++) {
			nxt[i][k][j]=nxt[i][nxt[i][k][j-1]][j-1];
			sum[i][k][j]=sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1];
			if(sum[i][k][j]>1000000000) sum[i][k][j]=1000000000;
			mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-sum[i][k][j-1]);
		}
	}
	for(int i=N-1; i>=0; i--) DP[i]=DP[W[i]]+S[i];
}
 
long long simulate(int x, int z) {
	int k=x; ll v=z;
	for(int i=0; i<24; i++) {
		int kk=k; ll vv=v;
		for(int j=i-1; j>=0; j--) if(vv<=mx[i][kk][j]) {
			vv+=sum[i][kk][j], kk=nxt[i][kk][j];
			if(kk==N) break;
		}
		if(kk==N) {
			for(int j=i-1; j>=0; j--) if(nxt[i][k][j]!=N) v+=sum[i][k][j], k=nxt[i][k][j];
			if(k!=N) v+=sum[i][k][0], k=nxt[i][k][0];
			return v;
		}
		if(vv<(1<<(i+1))) {
			if(vv>=S[kk]) vv+=S[kk], kk=W[kk];
			else vv+=P[kk], kk=L[kk];
		}
		k=kk, v=vv;
	}
	return v+DP[k];
}

Compilation message

dungeons.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("O3")
      |

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 683832 KB Output is correct
2 Correct 165 ms 683808 KB Output is correct
3 Correct 181 ms 692556 KB Output is correct
4 Correct 701 ms 900240 KB Output is correct
5 Correct 176 ms 692308 KB Output is correct
6 Correct 681 ms 899924 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 688212 KB Output is correct
2 Runtime error 1381 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 688236 KB Output is correct
2 Correct 1010 ms 899924 KB Output is correct
3 Correct 962 ms 900176 KB Output is correct
4 Correct 1006 ms 899972 KB Output is correct
5 Correct 964 ms 899976 KB Output is correct
6 Correct 973 ms 899976 KB Output is correct
7 Correct 1002 ms 899976 KB Output is correct
8 Correct 1490 ms 899968 KB Output is correct
9 Correct 848 ms 899980 KB Output is correct
10 Correct 1379 ms 899920 KB Output is correct
11 Correct 1837 ms 900132 KB Output is correct
12 Correct 4645 ms 899720 KB Output is correct
13 Correct 4582 ms 899976 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 688236 KB Output is correct
2 Correct 1010 ms 899924 KB Output is correct
3 Correct 962 ms 900176 KB Output is correct
4 Correct 1006 ms 899972 KB Output is correct
5 Correct 964 ms 899976 KB Output is correct
6 Correct 973 ms 899976 KB Output is correct
7 Correct 1002 ms 899976 KB Output is correct
8 Correct 1490 ms 899968 KB Output is correct
9 Correct 848 ms 899980 KB Output is correct
10 Correct 1379 ms 899920 KB Output is correct
11 Correct 1837 ms 900132 KB Output is correct
12 Correct 4645 ms 899720 KB Output is correct
13 Correct 4582 ms 899976 KB Output is correct
14 Correct 168 ms 688208 KB Output is correct
15 Correct 945 ms 899968 KB Output is correct
16 Correct 1029 ms 899816 KB Output is correct
17 Correct 1158 ms 900180 KB Output is correct
18 Correct 1154 ms 899868 KB Output is correct
19 Correct 985 ms 899968 KB Output is correct
20 Correct 1160 ms 900104 KB Output is correct
21 Correct 1357 ms 899924 KB Output is correct
22 Correct 1368 ms 900180 KB Output is correct
23 Correct 2347 ms 899920 KB Output is correct
24 Correct 2473 ms 900180 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 688236 KB Output is correct
2 Correct 1010 ms 899924 KB Output is correct
3 Correct 962 ms 900176 KB Output is correct
4 Correct 1006 ms 899972 KB Output is correct
5 Correct 964 ms 899976 KB Output is correct
6 Correct 973 ms 899976 KB Output is correct
7 Correct 1002 ms 899976 KB Output is correct
8 Correct 1490 ms 899968 KB Output is correct
9 Correct 848 ms 899980 KB Output is correct
10 Correct 1379 ms 899920 KB Output is correct
11 Correct 1837 ms 900132 KB Output is correct
12 Correct 4645 ms 899720 KB Output is correct
13 Correct 4582 ms 899976 KB Output is correct
14 Correct 168 ms 688208 KB Output is correct
15 Correct 945 ms 899968 KB Output is correct
16 Correct 1029 ms 899816 KB Output is correct
17 Correct 1158 ms 900180 KB Output is correct
18 Correct 1154 ms 899868 KB Output is correct
19 Correct 985 ms 899968 KB Output is correct
20 Correct 1160 ms 900104 KB Output is correct
21 Correct 1357 ms 899924 KB Output is correct
22 Correct 1368 ms 900180 KB Output is correct
23 Correct 2347 ms 899920 KB Output is correct
24 Correct 2473 ms 900180 KB Output is correct
25 Correct 720 ms 899160 KB Output is correct
26 Correct 1065 ms 899928 KB Output is correct
27 Correct 932 ms 900076 KB Output is correct
28 Correct 965 ms 900180 KB Output is correct
29 Correct 1057 ms 899968 KB Output is correct
30 Correct 1276 ms 899968 KB Output is correct
31 Correct 1398 ms 899788 KB Output is correct
32 Correct 1655 ms 899948 KB Output is correct
33 Correct 941 ms 899892 KB Output is correct
34 Correct 1663 ms 899748 KB Output is correct
35 Correct 1097 ms 899784 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 688212 KB Output is correct
2 Runtime error 1381 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -