oj.uz

답안 #921251

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921251 2024-02-03T15:38:26 Z byunjaewoo 던전 (IOI21_dungeons) C++17
63 / 100
 3011 ms 739280 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

const int Nmax=50010;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll nxt[25][25][Nmax], sum[25][25][Nmax], mx[25][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++) {
			if(S[j]>=(1<<(i+1))) nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=(1<<(i+1))-1-P[j];
			else if(S[j]<=(1<<i)) nxt[i][0][j]=W[j], sum[i][0][j]=S[j], mx[i][0][j]=(1<<(i+1))-1-S[j];
			else nxt[i][0][j]=L[j], sum[i][0][j]=P[j], mx[i][0][j]=min(S[j]-1, (1<<(i+1))-1-P[j]);
		}
		nxt[i][0][N]=N, sum[i][0][N]=0, mx[i][0][N]=(1<<(i+1))-1;
		for(int j=1; j<25; j++) for(int k=0; k<=N; k++) {
			nxt[i][j][k]=nxt[i][j-1][nxt[i][j-1][k]];
			sum[i][j][k]=sum[i][j-1][k]+sum[i][j-1][nxt[i][j-1][k]];
			mx[i][j][k]=min(mx[i][j-1][k], mx[i][j-1][nxt[i][j-1][k]]-sum[i][j-1][k]);
		}
	}
	for(int j=0; j<25; j++) for(int k=0; k<=N; k++) mx[24][j][k]=LLONG_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=24; j>=0; j--) if(vv<=mx[i][j][kk]) vv+=sum[i][j][kk], kk=nxt[i][j][kk];
		if(kk==N) {
			for(int j=24; j>=0; j--) if(nxt[i][j][k]!=N) v+=sum[i][j][k], k=nxt[i][j][k];
			if(k!=N) v+=sum[i][0][k], k=nxt[i][0][k];
			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:45:1: warning: control reaches end of non-void function [-Wreturn-type]
   45 | }
      | ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 398512 KB Output is correct
2 Correct 53 ms 402516 KB Output is correct
3 Correct 59 ms 416080 KB Output is correct
4 Correct 272 ms 736552 KB Output is correct
5 Correct 62 ms 421968 KB Output is correct
6 Correct 258 ms 737660 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 413248 KB Output is correct
2 Runtime error 131 ms 17964 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 413264 KB Output is correct
2 Correct 839 ms 738820 KB Output is correct
3 Correct 838 ms 739280 KB Output is correct
4 Correct 776 ms 738652 KB Output is correct
5 Correct 775 ms 738608 KB Output is correct
6 Correct 1029 ms 738648 KB Output is correct
7 Correct 1136 ms 738764 KB Output is correct
8 Correct 1160 ms 738504 KB Output is correct
9 Correct 566 ms 738516 KB Output is correct
10 Correct 1055 ms 738428 KB Output is correct
11 Correct 1321 ms 738428 KB Output is correct
12 Correct 2876 ms 739032 KB Output is correct
13 Correct 3011 ms 739008 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 413264 KB Output is correct
2 Correct 839 ms 738820 KB Output is correct
3 Correct 838 ms 739280 KB Output is correct
4 Correct 776 ms 738652 KB Output is correct
5 Correct 775 ms 738608 KB Output is correct
6 Correct 1029 ms 738648 KB Output is correct
7 Correct 1136 ms 738764 KB Output is correct
8 Correct 1160 ms 738504 KB Output is correct
9 Correct 566 ms 738516 KB Output is correct
10 Correct 1055 ms 738428 KB Output is correct
11 Correct 1321 ms 738428 KB Output is correct
12 Correct 2876 ms 739032 KB Output is correct
13 Correct 3011 ms 739008 KB Output is correct
14 Correct 62 ms 421204 KB Output is correct
15 Correct 781 ms 738876 KB Output is correct
16 Correct 840 ms 739200 KB Output is correct
17 Correct 1006 ms 738560 KB Output is correct
18 Correct 959 ms 738640 KB Output is correct
19 Correct 965 ms 738732 KB Output is correct
20 Correct 979 ms 738476 KB Output is correct
21 Correct 1135 ms 738580 KB Output is correct
22 Correct 1146 ms 738640 KB Output is correct
23 Correct 1478 ms 738892 KB Output is correct
24 Correct 1836 ms 738700 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 413264 KB Output is correct
2 Correct 839 ms 738820 KB Output is correct
3 Correct 838 ms 739280 KB Output is correct
4 Correct 776 ms 738652 KB Output is correct
5 Correct 775 ms 738608 KB Output is correct
6 Correct 1029 ms 738648 KB Output is correct
7 Correct 1136 ms 738764 KB Output is correct
8 Correct 1160 ms 738504 KB Output is correct
9 Correct 566 ms 738516 KB Output is correct
10 Correct 1055 ms 738428 KB Output is correct
11 Correct 1321 ms 738428 KB Output is correct
12 Correct 2876 ms 739032 KB Output is correct
13 Correct 3011 ms 739008 KB Output is correct
14 Correct 62 ms 421204 KB Output is correct
15 Correct 781 ms 738876 KB Output is correct
16 Correct 840 ms 739200 KB Output is correct
17 Correct 1006 ms 738560 KB Output is correct
18 Correct 959 ms 738640 KB Output is correct
19 Correct 965 ms 738732 KB Output is correct
20 Correct 979 ms 738476 KB Output is correct
21 Correct 1135 ms 738580 KB Output is correct
22 Correct 1146 ms 738640 KB Output is correct
23 Correct 1478 ms 738892 KB Output is correct
24 Correct 1836 ms 738700 KB Output is correct
25 Correct 275 ms 738060 KB Output is correct
26 Correct 826 ms 739160 KB Output is correct
27 Correct 782 ms 738528 KB Output is correct
28 Correct 794 ms 738552 KB Output is correct
29 Correct 896 ms 739092 KB Output is correct
30 Correct 1102 ms 738852 KB Output is correct
31 Correct 1257 ms 738388 KB Output is correct
32 Correct 1421 ms 738644 KB Output is correct
33 Correct 999 ms 738956 KB Output is correct
34 Correct 1866 ms 738708 KB Output is correct
35 Correct 1052 ms 738660 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 413248 KB Output is correct
2 Runtime error 131 ms 17964 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -