Submission #629774

#	Time	Username	Problem	Language	Result	Execution time	Memory
629774		Cross_Ratio	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7012 ms	234984 KiB

dungeons

#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 (stderr)

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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11