제출 #761528

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
761528		caganyanmaz	던전 (IOI21_dungeons)	C++17	0 / 100	7059 ms	2388 KiB

dungeons

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

constexpr static int SIZE = 400001;
constexpr static int LOG_SIZE = 30;
constexpr static int DIFF = 6; // Smaller than all, bigger than 1 2 3 4 5
int64_t gain[SIZE][DIFF][LOG_SIZE];
int nxt[SIZE][DIFF][LOG_SIZE];
vector<int> ds, s, p, w, l;
int m, n;

int gi(int val)
{
        return lower_bound(ds.begin(), ds.end(), val) - ds.begin();
}

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll)
{
        n = nn;
        s = ss, p = pp, w = ww, l = ll;
        set<int> dss;
        for (int i : s)
                dss.insert(i);
        assert(dss.size() <= 5);
        ds.pb(0);
        for (int i : dss)
                ds.pb(i);
        m = ds.size();
        p.pb(0), s.pb(0), w.pb(n), l.pb(n);
        for (int i = 0; i <= n; i++)
        {
                for (int j = 0; j < m; j++)
                {
                        if (gi(s[i]) > j)
                        {
                                gain[i][j][0] = p[i];
                                nxt[i][j][0] = l[i];
                        }
                        else
                        {
                                gain[i][j][0] = s[i];
                                nxt[i][j][0] = w[i];
                        }
                }
        }
        for (int i = 1; i < LOG_SIZE; i++)
        {
                for (int j = 0; j <= n; j++)
                {
                        for (int k = 0; k < m; k++)
                        {
                                nxt[j][k][i] = nxt[nxt[j][k][i-1]][k][i-1];
                                gain[j][k][i] = gain[j][k][i-1] + gain[nxt[j][k][i-1]][k][i-1];
                        }
                }
        }
}

int64_t simulate(int x, int zz)
{
        int64_t z = zz;
        while (x != n)
        {
                int _next = LOG_SIZE -1;
                int ci = gi(z);
                if (ci != m-1)
                        while (_next >= 0 && (gain[x][ci][_next] + z) < ds[ci+1]) _next--;
                if (_next >= 0)
                {
                        z += gain[x][ci][_next];
                        x = nxt[x][ci][_next];
                }
                if (x != n)
                {
                        if (z >= s[x])
                        {
                                z += s[x];
                                x = w[x];
                        }
                        else
                        {
                                z += p[x];
                                x = l[x];
                        }
                }
        }
        return z;
}

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