Submission #501566

#	Time	Username	Problem	Language	Result	Execution time	Memory
501566		ETK	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3000 ms	1127524 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define pb push_back
using namespace std;
const int inf = 0x3f3f3f3f,N = 4e5 + 5,B = 16,L = 7;
//The key observation is that every time we win our damage doubles
struct info{
    //next place and the attack you need to win a game
    int nxt,atk;
    //overall attack we gained
    ll sum;
    info operator + (const info a)const{
        int res;
        if(a.atk == inf)res = atk;
        else res = max(0ll,min((ll)atk,a.atk - sum));
        return (info){a.nxt,res,sum + a.sum};
    }
}f[L][25][N];
int n,powB[L];
vi s,p,w,l;
ll simulate(int x,int z_){
    ll z = z_;
    int i = 0;
    while(114514){
        while(i + 1 < L && z > powB[i+1]) i++;
        for(int j = 24;j >= 0;j--){
            info now = f[i][j][x];
            if(now.nxt == n)continue;//jumping too far
            if(now.atk != inf && now.atk <= z)continue;
            z += now.sum, x = now.nxt;
        }
        if(z >= s[x]) z += s[x], x = w[x];
        else z += p[x], x = l[x];
        if(x == n)return z;
    }
}
void prework(int X,int k){
    for(int i = 0;i < n;i++){
        if(X >= s[i]){
            f[k][0][i] = (info){w[i],inf,s[i]};
        }else f[k][0][i] = (info){l[i],s[i],p[i]};
    }
    for(int j = 1;j < 25;j++)for(int i = 0;i < n;i++){
        info t = f[k][j-1][i];
        f[k][j][i] = t + f[k][j-1][t.nxt];
    }
}
void init(int _n,vi _s,vi _p,vi _w,vi _l){
    n = _n,s = _s,p = _p,w = _w,l = _l;
    w.pb(n),l.pb(n);
    powB[0] = 1;
    prework(1,0);
    for(int d = 1;d < L;d++){
        powB[d] = powB[d-1] * B;
        prework(powB[d],d);
    }
}

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