oj.uz

Submission #622578

# Submission time Handle Problem Language Result Execution time Memory
622578 2022-08-04T11:54:20 Z jiahng Dungeons Game (IOI21_dungeons) C++17
63 / 100
 6075 ms 1732396 KB 
#include "dungeons.h"
#include <vector>
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define int ll
typedef pair<int32_t, ll> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 50010
#define maxb1 61
#define maxb2 20
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
 
pi dp[maxn][maxb1][maxb2]; // (ending node, added val) if start at i and do 2^k steps winning if 2^j >= S
int mx[maxn][maxb1][maxb2]; // max z for dp[i][j][k] to be accurate
 
int S[maxn], P[maxn], W[maxn], L[maxn];
int N;
inline int msb(int x){
    return 63 - __builtin_clzl(x);
}
void init(int32_t n, std::vector<int32_t> s, std::vector<int32_t> p, std::vector<int32_t> w, std::vector<int32_t> l) {
 
    N = n;
    FOR(i,0,N-1){
        S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
    }
    FOR(i,0,N-1) FOR(j,0,maxb1-1){
        if ((1LL << j) >= S[i]) dp[i][j][0] = pi(W[i], S[i]);
        else dp[i][j][0] = pi(L[i], P[i]);
        if (S[i] > (1LL << j)) mx[i][j][0] = S[i] - 1;
        else mx[i][j][0] = INF;
    }
    FOR(j,0,maxb1-1) dp[N][j][0] = pi(N, 0);
 
    FOR(k,1,maxb2-1) FOR(j,0,maxb1-1){
        FOR(i,0,N){
            dp[i][j][k] = dp[dp[i][j][k-1].f][j][k-1];
            dp[i][j][k].s += dp[i][j][k-1].s;
            mx[i][j][k] = min(mx[i][j][k-1], mx[dp[i][j][k-1].f][j][k-1] - dp[i][j][k-1].s);
        }
    }
	return;
}
 
 
long long simulate(int32_t x, int32_t _z) {
    ll z = _z;
    while (1){
        //cout << msb(z) << ' ';
        //cout << x << ' ';
        int a = msb(z);
        DEC(k,maxb2-1,0) if (z <= mx[x][msb(z)][k] && dp[x][msb(z)][k].f < N){
           pi val = dp[x][msb(z)][k];
           z += val.s;; 
           x = val.f;
        }
        //cout << x << ' ';
 
        //cout << x << ' ' << z << '\n';
        if (z >= S[x] && W[x] == N) return z + S[x];
        if (z < S[x] && L[x] == N) return z + P[x];
           
        //cout << z << ' ';
        if (z >= S[x]){
            z += S[x];
            x = W[x];
        }else{
            z += P[x];
            x = L[x];
        }
        //cout << x << ' ';
        //cout << zz << ' ' << z << '\n';
        //assert(msb(z) >= a+1);
 
    }
	return 0;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int32_t, int32_t)':
dungeons.cpp:74:13: warning: unused variable 'a' [-Wunused-variable]
   74 |         int a = msb(z);
      |             ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 568 KB Output is correct
3 Correct 134 ms 57772 KB Output is correct
4 Correct 3734 ms 1437112 KB Output is correct
5 Correct 124 ms 57800 KB Output is correct
6 Correct 3642 ms 1436948 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 29012 KB Output is correct
2 Runtime error 1340 ms 1732396 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 29012 KB Output is correct
2 Correct 3758 ms 1436736 KB Output is correct
3 Correct 3601 ms 1436848 KB Output is correct
4 Correct 3729 ms 1437984 KB Output is correct
5 Correct 3477 ms 1437740 KB Output is correct
6 Correct 3717 ms 1438108 KB Output is correct
7 Correct 3847 ms 1438028 KB Output is correct
8 Correct 3674 ms 1437740 KB Output is correct
9 Correct 3773 ms 1437744 KB Output is correct
10 Correct 3447 ms 1437616 KB Output is correct
11 Correct 4497 ms 1437992 KB Output is correct
12 Correct 6075 ms 1437980 KB Output is correct
13 Correct 4907 ms 1438000 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 29012 KB Output is correct
2 Correct 3758 ms 1436736 KB Output is correct
3 Correct 3601 ms 1436848 KB Output is correct
4 Correct 3729 ms 1437984 KB Output is correct
5 Correct 3477 ms 1437740 KB Output is correct
6 Correct 3717 ms 1438108 KB Output is correct
7 Correct 3847 ms 1438028 KB Output is correct
8 Correct 3674 ms 1437740 KB Output is correct
9 Correct 3773 ms 1437744 KB Output is correct
10 Correct 3447 ms 1437616 KB Output is correct
11 Correct 4497 ms 1437992 KB Output is correct
12 Correct 6075 ms 1437980 KB Output is correct
13 Correct 4907 ms 1438000 KB Output is correct
14 Correct 64 ms 29096 KB Output is correct
15 Correct 3599 ms 1438204 KB Output is correct
16 Correct 3797 ms 1438364 KB Output is correct
17 Correct 3412 ms 1437860 KB Output is correct
18 Correct 3445 ms 1437868 KB Output is correct
19 Correct 3754 ms 1437996 KB Output is correct
20 Correct 3415 ms 1437904 KB Output is correct
21 Correct 3384 ms 1437884 KB Output is correct
22 Correct 3389 ms 1437868 KB Output is correct
23 Correct 4387 ms 1437992 KB Output is correct
24 Correct 4623 ms 1437968 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 29012 KB Output is correct
2 Correct 3758 ms 1436736 KB Output is correct
3 Correct 3601 ms 1436848 KB Output is correct
4 Correct 3729 ms 1437984 KB Output is correct
5 Correct 3477 ms 1437740 KB Output is correct
6 Correct 3717 ms 1438108 KB Output is correct
7 Correct 3847 ms 1438028 KB Output is correct
8 Correct 3674 ms 1437740 KB Output is correct
9 Correct 3773 ms 1437744 KB Output is correct
10 Correct 3447 ms 1437616 KB Output is correct
11 Correct 4497 ms 1437992 KB Output is correct
12 Correct 6075 ms 1437980 KB Output is correct
13 Correct 4907 ms 1438000 KB Output is correct
14 Correct 64 ms 29096 KB Output is correct
15 Correct 3599 ms 1438204 KB Output is correct
16 Correct 3797 ms 1438364 KB Output is correct
17 Correct 3412 ms 1437860 KB Output is correct
18 Correct 3445 ms 1437868 KB Output is correct
19 Correct 3754 ms 1437996 KB Output is correct
20 Correct 3415 ms 1437904 KB Output is correct
21 Correct 3384 ms 1437884 KB Output is correct
22 Correct 3389 ms 1437868 KB Output is correct
23 Correct 4387 ms 1437992 KB Output is correct
24 Correct 4623 ms 1437968 KB Output is correct
25 Correct 3685 ms 1437532 KB Output is correct
26 Correct 3754 ms 1438396 KB Output is correct
27 Correct 3645 ms 1437888 KB Output is correct
28 Correct 3658 ms 1437856 KB Output is correct
29 Correct 3924 ms 1438264 KB Output is correct
30 Correct 3534 ms 1438120 KB Output is correct
31 Correct 3556 ms 1438000 KB Output is correct
32 Correct 4499 ms 1437876 KB Output is correct
33 Correct 3799 ms 1437456 KB Output is correct
34 Correct 4440 ms 1437372 KB Output is correct
35 Correct 4145 ms 1438152 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 29012 KB Output is correct
2 Runtime error 1340 ms 1732396 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -