Submission #825275

#	Time	Username	Problem	Language	Result	Execution time	Memory
825275		TheSahib	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	231 ms	317584 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, ll>

const int MAX = 4e5 + 5;
const int LOGMAX = 30;
const int oo = 1e9 + 9;


int n;

struct G{
    pii par[LOGMAX + 1][MAX];
    void preCalc(){
        for (int j = 1; j <= LOGMAX; j++)
        {
            for (int i = 0; i <= n; i++)
            {
                int m = par[j - 1][i].first;
                if(m == -1){
                    par[j][i] = par[j - 1][i];
                    continue;
                }
                if(par[j - 1][m].first == -1){
                    par[j][i] = par[j - 1][m];
                    continue;
                }
                par[j][i].first = par[j - 1][m].first;
                par[j][i].second = par[j - 1][i].second + par[j - 1][m].second;
            }
        }
    }
    pii lift(ll start, ll target, int v){
        if(start >= target || v == -1) return {v, start};
        for(int j = LOGMAX; j >= 0; --j){
            ll a = start + par[j][v].second;
            if(a < target && par[j][v].first != -1){
                start = a;
                v = par[j][v].first;
            }
        }
        return {par[0][v].first, par[0][v].second + start};
    }
};

vector<ll> v;
G gs[10];

void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    n = N;
    set<int> st;
    for (int i = 0; i < n; i++)
    {
        st.insert(s[i]);
    }
    st.insert(-1);
    for(auto& p:st){
        v.push_back(p);
    }

    
    for (int i = 0; i < v.size(); i++)
    {
        for(int j = 0; j <= N; ++j){
            if(j == N){
                gs[i].par[0][j] = {-1, 0};
                continue;
            }
            if(s[j] > v[i]){
                gs[i].par[0][j] = {l[j], p[j]};
            }
            else{
                gs[i].par[0][j] = {w[j], s[j]};
            }
        }
        gs[i].preCalc();
    }
    v.push_back(1ll * oo * oo);
    return;
}

ll simulate(int x, int z) {
    ll u = x;
    ll s = z;
	for (int i = 0; i < v.size() - 1; i++)
    {
        pii p = gs[i].lift(s, v[i + 1], u);
        u = p.first;
        s = p.second;
    }
    return s;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < v.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~

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