oj.uz

답안 #921272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921272 2024-02-03T15:59:45 Z byunjaewoo 던전 (IOI21_dungeons) C++17
63 / 100
 5239 ms 2097152 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=400010;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
vector<int> nxt[25][Nmax], mx[25][Nmax];
vector<ll> sum[25][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<25; i++) for(int j=0; j<=N; j++) nxt[i][j].resize(i+1), mx[i][j].resize(i+1), sum[i][j].resize(i+1);
	for(int i=0; i<25; 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];
			mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-(int)min((ll)INT_MAX, sum[i][k][j-1]));
		}
	}
	for(int j=0; j<25; j++) for(int k=0; k<=N; k++) mx[24][k][j]=INT_MAX;
}
 
long long simulate(int x, int z) {
	int k=x; ll v=z;
	for(int i=0; i<25; i++) {
		int kk=k; ll vv=v;
		for(int j=i; 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; 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;
	}
}

Compilation message

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

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 710592 KB Output is correct
2 Correct 188 ms 710604 KB Output is correct
3 Correct 200 ms 722928 KB Output is correct
4 Correct 1010 ms 1019992 KB Output is correct
5 Correct 192 ms 722808 KB Output is correct
6 Correct 1025 ms 1019928 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 716624 KB Output is correct
2 Runtime error 1477 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 716808 KB Output is correct
2 Correct 1284 ms 1021536 KB Output is correct
3 Correct 1234 ms 1021424 KB Output is correct
4 Correct 1402 ms 1020916 KB Output is correct
5 Correct 1321 ms 1020808 KB Output is correct
6 Correct 1232 ms 1021264 KB Output is correct
7 Correct 1335 ms 1021064 KB Output is correct
8 Correct 2103 ms 1020932 KB Output is correct
9 Correct 969 ms 1020600 KB Output is correct
10 Correct 1824 ms 1020684 KB Output is correct
11 Correct 2340 ms 1021068 KB Output is correct
12 Correct 5239 ms 1021108 KB Output is correct
13 Correct 5065 ms 1021064 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 716808 KB Output is correct
2 Correct 1284 ms 1021536 KB Output is correct
3 Correct 1234 ms 1021424 KB Output is correct
4 Correct 1402 ms 1020916 KB Output is correct
5 Correct 1321 ms 1020808 KB Output is correct
6 Correct 1232 ms 1021264 KB Output is correct
7 Correct 1335 ms 1021064 KB Output is correct
8 Correct 2103 ms 1020932 KB Output is correct
9 Correct 969 ms 1020600 KB Output is correct
10 Correct 1824 ms 1020684 KB Output is correct
11 Correct 2340 ms 1021068 KB Output is correct
12 Correct 5239 ms 1021108 KB Output is correct
13 Correct 5065 ms 1021064 KB Output is correct
14 Correct 210 ms 716624 KB Output is correct
15 Correct 1411 ms 1021196 KB Output is correct
16 Correct 1294 ms 1021324 KB Output is correct
17 Correct 1884 ms 1020928 KB Output is correct
18 Correct 1623 ms 1020936 KB Output is correct
19 Correct 1643 ms 1021068 KB Output is correct
20 Correct 1650 ms 1020808 KB Output is correct
21 Correct 1588 ms 1020936 KB Output is correct
22 Correct 2354 ms 1020940 KB Output is correct
23 Correct 3086 ms 1021332 KB Output is correct
24 Correct 3323 ms 1021068 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 716808 KB Output is correct
2 Correct 1284 ms 1021536 KB Output is correct
3 Correct 1234 ms 1021424 KB Output is correct
4 Correct 1402 ms 1020916 KB Output is correct
5 Correct 1321 ms 1020808 KB Output is correct
6 Correct 1232 ms 1021264 KB Output is correct
7 Correct 1335 ms 1021064 KB Output is correct
8 Correct 2103 ms 1020932 KB Output is correct
9 Correct 969 ms 1020600 KB Output is correct
10 Correct 1824 ms 1020684 KB Output is correct
11 Correct 2340 ms 1021068 KB Output is correct
12 Correct 5239 ms 1021108 KB Output is correct
13 Correct 5065 ms 1021064 KB Output is correct
14 Correct 210 ms 716624 KB Output is correct
15 Correct 1411 ms 1021196 KB Output is correct
16 Correct 1294 ms 1021324 KB Output is correct
17 Correct 1884 ms 1020928 KB Output is correct
18 Correct 1623 ms 1020936 KB Output is correct
19 Correct 1643 ms 1021068 KB Output is correct
20 Correct 1650 ms 1020808 KB Output is correct
21 Correct 1588 ms 1020936 KB Output is correct
22 Correct 2354 ms 1020940 KB Output is correct
23 Correct 3086 ms 1021332 KB Output is correct
24 Correct 3323 ms 1021068 KB Output is correct
25 Correct 966 ms 1020356 KB Output is correct
26 Correct 1267 ms 1021436 KB Output is correct
27 Correct 1443 ms 1020812 KB Output is correct
28 Correct 1147 ms 1020756 KB Output is correct
29 Correct 1433 ms 1021324 KB Output is correct
30 Correct 1746 ms 1020944 KB Output is correct
31 Correct 1869 ms 1020804 KB Output is correct
32 Correct 1872 ms 1020944 KB Output is correct
33 Correct 1166 ms 1020752 KB Output is correct
34 Correct 2263 ms 1020816 KB Output is correct
35 Correct 1711 ms 1021308 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 716624 KB Output is correct
2 Runtime error 1477 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -