oj.uz

답안 #921278

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921278 2024-02-03T16:04:54 Z byunjaewoo 던전 (IOI21_dungeons) C++17
11 / 100
 1446 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], 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), mx[i][j].resize(i), sum[i][j].resize(i);
	for(int i=1; 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];
			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 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-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;
	}
}

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 192 ms 710484 KB Output is correct
2 Correct 167 ms 710484 KB Output is correct
3 Correct 184 ms 719696 KB Output is correct
4 Correct 767 ms 943480 KB Output is correct
5 Correct 180 ms 719712 KB Output is correct
6 Correct 731 ms 943080 KB Output is correct

Subtask #2
0.0 / 26.0

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

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 715136 KB Output is correct
2 Correct 1029 ms 942848 KB Output is correct
3 Incorrect 1060 ms 942908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 715136 KB Output is correct
2 Correct 1029 ms 942848 KB Output is correct
3 Incorrect 1060 ms 942908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 715136 KB Output is correct
2 Correct 1029 ms 942848 KB Output is correct
3 Incorrect 1060 ms 942908 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

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