oj.uz

Submission #538989

# Submission time Handle Problem Language Result Execution time Memory
538989 2022-03-18T06:50:52 Z balbit Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3425 ms 2061532 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7380 KB Output is correct
2 Correct 4 ms 7500 KB Output is correct
3 Correct 10 ms 17728 KB Output is correct
4 Correct 177 ms 264248 KB Output is correct
5 Correct 11 ms 17756 KB Output is correct
6 Correct 181 ms 264152 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12628 KB Output is correct
2 Correct 1423 ms 2050020 KB Output is correct
3 Correct 1349 ms 2056688 KB Output is correct
4 Correct 1349 ms 2056092 KB Output is correct
5 Correct 1424 ms 2053436 KB Output is correct
6 Correct 1447 ms 2049216 KB Output is correct
7 Correct 1439 ms 2054756 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12632 KB Output is correct
2 Correct 240 ms 265132 KB Output is correct
3 Correct 238 ms 264660 KB Output is correct
4 Correct 206 ms 264296 KB Output is correct
5 Correct 199 ms 264324 KB Output is correct
6 Correct 272 ms 264396 KB Output is correct
7 Correct 311 ms 264488 KB Output is correct
8 Correct 231 ms 264312 KB Output is correct
9 Correct 210 ms 264184 KB Output is correct
10 Correct 221 ms 264212 KB Output is correct
11 Correct 246 ms 264208 KB Output is correct
12 Correct 339 ms 264540 KB Output is correct
13 Correct 252 ms 264412 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12632 KB Output is correct
2 Correct 240 ms 265132 KB Output is correct
3 Correct 238 ms 264660 KB Output is correct
4 Correct 206 ms 264296 KB Output is correct
5 Correct 199 ms 264324 KB Output is correct
6 Correct 272 ms 264396 KB Output is correct
7 Correct 311 ms 264488 KB Output is correct
8 Correct 231 ms 264312 KB Output is correct
9 Correct 210 ms 264184 KB Output is correct
10 Correct 221 ms 264212 KB Output is correct
11 Correct 246 ms 264208 KB Output is correct
12 Correct 339 ms 264540 KB Output is correct
13 Correct 252 ms 264412 KB Output is correct
14 Correct 7 ms 12628 KB Output is correct
15 Correct 221 ms 264348 KB Output is correct
16 Correct 244 ms 264360 KB Output is correct
17 Correct 202 ms 264460 KB Output is correct
18 Correct 198 ms 264428 KB Output is correct
19 Correct 293 ms 264440 KB Output is correct
20 Correct 230 ms 264364 KB Output is correct
21 Correct 233 ms 264396 KB Output is correct
22 Correct 222 ms 264152 KB Output is correct
23 Correct 246 ms 264268 KB Output is correct
24 Correct 338 ms 264368 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12632 KB Output is correct
2 Correct 240 ms 265132 KB Output is correct
3 Correct 238 ms 264660 KB Output is correct
4 Correct 206 ms 264296 KB Output is correct
5 Correct 199 ms 264324 KB Output is correct
6 Correct 272 ms 264396 KB Output is correct
7 Correct 311 ms 264488 KB Output is correct
8 Correct 231 ms 264312 KB Output is correct
9 Correct 210 ms 264184 KB Output is correct
10 Correct 221 ms 264212 KB Output is correct
11 Correct 246 ms 264208 KB Output is correct
12 Correct 339 ms 264540 KB Output is correct
13 Correct 252 ms 264412 KB Output is correct
14 Correct 7 ms 12628 KB Output is correct
15 Correct 221 ms 264348 KB Output is correct
16 Correct 244 ms 264360 KB Output is correct
17 Correct 202 ms 264460 KB Output is correct
18 Correct 198 ms 264428 KB Output is correct
19 Correct 293 ms 264440 KB Output is correct
20 Correct 230 ms 264364 KB Output is correct
21 Correct 233 ms 264396 KB Output is correct
22 Correct 222 ms 264152 KB Output is correct
23 Correct 246 ms 264268 KB Output is correct
24 Correct 338 ms 264368 KB Output is correct
25 Correct 184 ms 263192 KB Output is correct
26 Correct 252 ms 264448 KB Output is correct
27 Correct 221 ms 264412 KB Output is correct
28 Correct 244 ms 264324 KB Output is correct
29 Correct 272 ms 264396 KB Output is correct
30 Correct 262 ms 264428 KB Output is correct
31 Correct 258 ms 264396 KB Output is correct
32 Correct 395 ms 264412 KB Output is correct
33 Correct 804 ms 264648 KB Output is correct
34 Correct 1377 ms 265824 KB Output is correct
35 Correct 669 ms 265932 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12628 KB Output is correct
2 Correct 1423 ms 2050020 KB Output is correct
3 Correct 1349 ms 2056688 KB Output is correct
4 Correct 1349 ms 2056092 KB Output is correct
5 Correct 1424 ms 2053436 KB Output is correct
6 Correct 1447 ms 2049216 KB Output is correct
7 Correct 1439 ms 2054756 KB Output is correct
8 Correct 7 ms 12632 KB Output is correct
9 Correct 240 ms 265132 KB Output is correct
10 Correct 238 ms 264660 KB Output is correct
11 Correct 206 ms 264296 KB Output is correct
12 Correct 199 ms 264324 KB Output is correct
13 Correct 272 ms 264396 KB Output is correct
14 Correct 311 ms 264488 KB Output is correct
15 Correct 231 ms 264312 KB Output is correct
16 Correct 210 ms 264184 KB Output is correct
17 Correct 221 ms 264212 KB Output is correct
18 Correct 246 ms 264208 KB Output is correct
19 Correct 339 ms 264540 KB Output is correct
20 Correct 252 ms 264412 KB Output is correct
21 Correct 7 ms 12628 KB Output is correct
22 Correct 221 ms 264348 KB Output is correct
23 Correct 244 ms 264360 KB Output is correct
24 Correct 202 ms 264460 KB Output is correct
25 Correct 198 ms 264428 KB Output is correct
26 Correct 293 ms 264440 KB Output is correct
27 Correct 230 ms 264364 KB Output is correct
28 Correct 233 ms 264396 KB Output is correct
29 Correct 222 ms 264152 KB Output is correct
30 Correct 246 ms 264268 KB Output is correct
31 Correct 338 ms 264368 KB Output is correct
32 Correct 184 ms 263192 KB Output is correct
33 Correct 252 ms 264448 KB Output is correct
34 Correct 221 ms 264412 KB Output is correct
35 Correct 244 ms 264324 KB Output is correct
36 Correct 272 ms 264396 KB Output is correct
37 Correct 262 ms 264428 KB Output is correct
38 Correct 258 ms 264396 KB Output is correct
39 Correct 395 ms 264412 KB Output is correct
40 Correct 804 ms 264648 KB Output is correct
41 Correct 1377 ms 265824 KB Output is correct
42 Correct 669 ms 265932 KB Output is correct
43 Correct 4 ms 7380 KB Output is correct
44 Correct 7 ms 12668 KB Output is correct
45 Correct 2023 ms 2061532 KB Output is correct
46 Correct 1559 ms 2056936 KB Output is correct
47 Correct 1725 ms 2057148 KB Output is correct
48 Correct 1506 ms 2059636 KB Output is correct
49 Correct 2161 ms 2061340 KB Output is correct
50 Correct 1395 ms 2058908 KB Output is correct
51 Correct 1415 ms 2059476 KB Output is correct
52 Correct 1380 ms 2056912 KB Output is correct
53 Correct 2908 ms 2057808 KB Output is correct
54 Correct 2310 ms 2058904 KB Output is correct
55 Correct 2832 ms 2057824 KB Output is correct
56 Correct 2939 ms 2058536 KB Output is correct
57 Correct 3123 ms 2058608 KB Output is correct
58 Correct 3425 ms 2058612 KB Output is correct
59 Correct 3381 ms 2058836 KB Output is correct
60 Correct 2432 ms 2058048 KB Output is correct
61 Correct 2282 ms 2058024 KB Output is correct