Submission #538989

#	Time	Username	Problem	Language	Result	Execution time	Memory
538989		balbit	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3425 ms	2061532 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
//#define int ll
//#define BALBIT
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
//const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 4e5+5;
const int MXVAL = 1e7+100;

vector<int> s, p, w, l;

const int nlay = 13;
const ll inf = 1ll<<60;

int yo[13][25][maxn]; // for this layer and this distance, minimum needed starting value to beat an s
ll gain[13][25][maxn]; // how much i gain[lay] from starting at v and walking 2^i steps
int to[13][25][maxn]; // where i get to after 2^i steps

void init(int n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
    s.swap(_s);
    p.swap(_p);
    w.swap(_w);
    l.swap(_l);

    for (int lay = 0; lay < 13; ++lay) {
        // working for current value in [4^lay, 4^(lay+1) )
        // now fill in base values
        REP(i,n+1) {
            if (i == n) {
                yo[lay][0][i] = -1;
                to[lay][0][i] = i;
                gain[lay][0][i] = 0;
            }else if( s[i] <= (1<<(lay*2))) {
                // auto win, gain[lay] s[i], disregarded
                gain[lay][0][i] = s[i];
                to[lay][0][i] = w[i];
                yo[lay][0][i] = MXVAL;
            }else{
                gain[lay][0][i] = p[i];
                to[lay][0][i] = l[i];
                yo[lay][0][i] = s[i];
            }
        }
        for (int j = 1; j < 25; ++j) {
            REP(i,n+1) {
                to[lay][j][i] = to[lay][j-1][to[lay][j-1][i]];
                gain[lay][j][i] = min(inf, gain[lay][j-1][i] + gain[lay][j-1][to[lay][j-1][i]]);
                ll rr = yo[lay][j-1][to[lay][j-1][i]];
                if (rr != MXVAL) rr -= gain[lay][j-1][i];
                yo[lay][j][i] = max(-1ll, min((ll)yo[lay][j-1][i], rr));
            }
        }
    }

//    assert(0);
	return;
}

long long simulate(int x, int _z) {

    ll z = _z;
    int lay = 0;
    while (1) {
        while ((1<<((lay+1)*2)) <= z && lay+1 < 13) ++lay;

//        ll nxt = 1ll<<((lay+1)*2);
//        if (lay == 12) nxt = 1ll<<62;
        for (int j = 24; j>=0; --j) {
            if (yo[lay][j][x] > z|| yo[lay][j][x]== MXVAL){// && z + gain[lay][j][x] < nxt) {
                // ダメだ
                z += gain[lay][j][x];
                x = to[lay][j][x];
            }else{
                // no jumping!
            }
        }
//        bug(lay, nxt, x, z);

        if (x == SZ(s)) return z;
//        assert(z >= s[x]);
        z += s[x]; x = w[x];
//        if (z >= s[x]) {
//            z += s[x];
//            x = w[x];
//        }else{
//            z += p[x];
//            x = l[x];
//        }
//        bug(lay, nxt, x, z);
        if (x == SZ(s)) return z;
    }

	return 0ll;
}

/*
3 3
2 6 9
3 1 2
2 2 3
1 0 1

*/

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