Submission #807819

#	Time	Username	Problem	Language	Result	Execution time	Memory
807819		vjudge1	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	208 ms	122532 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> S,P,W,L;
long long cost[6], N, bjto[6][100100][25], bjad[6][100100][25];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N=n,S=s,P=p,W=w,L=l;
    map<int, vector<int>> mp;
    for(int i = 0; i < n; i++)
        mp[s[i]].push_back(i);
    int cnt = 0;
    for(auto i: mp)
        cost[cnt++] = i.first;
    cost[cnt] = 1e18;
    for(int i = 0; i <= cnt; i++) {
        for(int j = 0; j < n; j++) {
            if(cost[i]>s[j]) {
                bjto[i][j][0]=w[j];
                bjad[i][j][0]=s[j];
            } else {
                bjto[i][j][0]=l[j];
                bjad[i][j][0]=p[j];
            }
        }
        bjto[i][n][0]=n;
        for(int k = 1; k < 25; k++) {
            for(int j = 0; j <= n; j++) {
                bjto[i][j][k]=bjto[i][bjto[i][j][k-1]][k-1];
                bjad[i][j][k]=bjad[i][j][k-1]+bjad[i][bjto[i][j][k-1]][k-1];
            }
        }
    }
	return;
}

long long simulate(int x, int Z) {
    long long z = Z;
    int lev = 0;
    while(x!=N) {
        while(z>=cost[lev]) lev++;
        for(int i = 25; i--;)
            if(z+bjad[lev][x][i]<cost[lev])
                z+=bjad[lev][x][i], x = bjto[lev][x][i];
        z+=bjad[lev][x][0];
        x=bjto[lev][x][0];
    }
    return z;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11