| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 538980 | balbit | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "dungeons.h"
#include <bits/stdc++.h>
//#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][24][maxn]; // for this layer and this distance, minimum needed starting value to beat an s
ll gain[13][24][maxn]; // how much i gain[lay] from starting at v and walking 2^i steps
int to[13][24][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 < 24; ++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(yo[lay][j-1][i], rr));
}
}
}
return;
}
long long simulate(int x, int _z) {
ll z = _z;
while (1) {
int lay = 0;
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 = 23; j>=0; --j) {
if (yo[lay][j][x] > z){// && 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]);
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
*/