oj.uz

답안 #629774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629774 2022-08-15T05:50:02 Z Cross_Ratio 던전 (IOI21_dungeons) C++17
37 / 100
 7000 ms 234984 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const long long int INF = 1e18;
int N;
long long int S[400005];
long long int I[400005];
int W[400005];
int L[400005];
int rpos[400005][26];
long long int rsum[400005][26];
long long int limit[400005][26];
void init(int _N, vector<int> _S, vector<int> _I, vector<int> _W, vector<int> _L) {
	N = _N;
	int i, j;
	//cout << "init\n";
	for(i=0;i<N;i++) {
        S[i] = _S[i];
        I[i] = _I[i];
        W[i] = _W[i];
        L[i] = _L[i];
	}
	S[N] = I[N] = 0;
	W[N] = L[N] = N;
	//cout << "init\n";
	for(i=0;i<=N;i++) {
        rpos[i][0] = W[i];
        rsum[i][0] = S[i];
        limit[i][0] = S[i];
	}
	for(i=1;i<26;i++) {
        for(j=0;j<=N;j++) {
            rpos[j][i] = rpos[rpos[j][i-1]][i-1];
            rsum[j][i] = rsum[j][i-1] + rsum[rpos[j][i-1]][i-1];
            limit[j][i] = max(limit[j][i-1],limit[rpos[j][i-1]][i-1] - rsum[j][i-1]);
        }
	}
}

long long simulate(int pos, int _power) {
	long long int power = _power;
	while(pos != N) {
        int i, j;
        for(i=25;i>=0;i--) {
            int pos2 = rpos[pos][i];
            long long int pow2 = rsum[pos][i];
            long long int lim2 = limit[pos][i];
            if(pos2 != N && power >= lim2) {
                pos = pos2;
                power += pow2;
            }
        }
        //cout << pos << ' ' << power << '\n';
        if(power >= S[pos]) {
            power += S[pos];
            pos = W[pos];
        }
        else {
            power += I[pos];
            pos = L[pos];
        }
        //cout << " state : " << pos << ' ' << power << '\n';
	}
	return power;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:43:16: warning: unused variable 'j' [-Wunused-variable]
   43 |         int i, j;
      |                ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 58 ms 29496 KB Output is correct
5 Correct 3 ms 1492 KB Output is correct
6 Correct 61 ms 29444 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 525 ms 233436 KB Output is correct
3 Correct 529 ms 233320 KB Output is correct
4 Correct 528 ms 234984 KB Output is correct
5 Correct 495 ms 234984 KB Output is correct
6 Correct 547 ms 233324 KB Output is correct
7 Correct 504 ms 231648 KB Output is correct

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 960 KB Output is correct
2 Correct 85 ms 30908 KB Output is correct
3 Correct 100 ms 31080 KB Output is correct
4 Correct 90 ms 30544 KB Output is correct
5 Correct 106 ms 30312 KB Output is correct
6 Execution timed out 7012 ms 30540 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 960 KB Output is correct
2 Correct 85 ms 30908 KB Output is correct
3 Correct 100 ms 31080 KB Output is correct
4 Correct 90 ms 30544 KB Output is correct
5 Correct 106 ms 30312 KB Output is correct
6 Execution timed out 7012 ms 30540 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 960 KB Output is correct
2 Correct 85 ms 30908 KB Output is correct
3 Correct 100 ms 31080 KB Output is correct
4 Correct 90 ms 30544 KB Output is correct
5 Correct 106 ms 30312 KB Output is correct
6 Execution timed out 7012 ms 30540 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 525 ms 233436 KB Output is correct
3 Correct 529 ms 233320 KB Output is correct
4 Correct 528 ms 234984 KB Output is correct
5 Correct 495 ms 234984 KB Output is correct
6 Correct 547 ms 233324 KB Output is correct
7 Correct 504 ms 231648 KB Output is correct
8 Correct 1 ms 960 KB Output is correct
9 Correct 85 ms 30908 KB Output is correct
10 Correct 100 ms 31080 KB Output is correct
11 Correct 90 ms 30544 KB Output is correct
12 Correct 106 ms 30312 KB Output is correct
13 Execution timed out 7012 ms 30540 KB Time limit exceeded
14 Halted 0 ms 0 KB -