oj.uz

Submission #937082

# Submission time Handle Problem Language Result Execution time Memory
937082 2024-03-03T12:42:58 Z GrindMachine Dungeons Game (IOI21_dungeons) C++17
63 / 100
 4461 ms 1158624 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
 
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)
 
template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}
 
template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}
 
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
 
/*
 
read some solutions long back and remember some ideas from there
 
*/
 
const int MOD = 1e9 + 7;
const int N = 5e4 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int LOG = 25;
 
#include "dungeons.h"
 
#define data DATA
 
struct data{
    ll sum,mx;
    data(){
        sum = 0;
        mx = -inf2;
    }
    data(ll x, ll y){
        sum = x;
        mx = y;
    }
};

data merge(data &left, data &right){
    data curr;
    curr.sum = left.sum + right.sum;
    curr.mx = max(left.mx,left.sum+right.mx);
    return curr;
}
 
int up[LOG][N][LOG];
data dat[LOG][N][LOG];
int n;
vector<int> s,p,w,l;
 
void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
    n = n_;
    s = s_;
    p = p_;
    w = w_;
    l = l_;
    
    rep(j,LOG){
        rep(i,n){
            if(s[i] < (1<<j)){
                // win
                up[j][i][0] = w[i];
                dat[j][i][0] = data(s[i],-inf2);
            }
            else{
                // lose
                up[j][i][0] = l[i];
                dat[j][i][0] = data(p[i],-s[i]);
            }
        }

        rep(k,LOG){
            up[j][n][k] = n;
            dat[j][n][k] = data();
        }

        rep1(k,LOG-1){
            rep(i,n){
                up[j][i][k] = up[j][up[j][i][k-1]][k-1];
                dat[j][i][k] = merge(dat[j][i][k-1],dat[j][up[j][i][k-1]][k-1]);
            }
        }
    }
}
 
long long simulate(int x, int z_) {
    ll z = z_;
    while(true){
        // find first win over a big guy
        int j = 63-__builtin_clzll(z);
        amin(j,24);

        rev(k,LOG-1,0){
            auto &d = dat[j][x][k];
            if(z+d.mx >= 0) conts;
            x = up[j][x][k];
            z += d.sum;
        }

        if(x == n) break;

        assert(z >= s[x]);
        assert(s[x] >= (1<<j));

        z += s[x];
        x = w[x];
    }

    return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 489788 KB Output is correct
2 Correct 172 ms 489924 KB Output is correct
3 Correct 179 ms 494916 KB Output is correct
4 Correct 501 ms 615228 KB Output is correct
5 Correct 181 ms 494932 KB Output is correct
6 Correct 509 ms 615252 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 492468 KB Output is correct
2 Runtime error 4461 ms 1158624 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 176 ms 492212 KB Output is correct
2 Correct 617 ms 616772 KB Output is correct
3 Correct 553 ms 616928 KB Output is correct
4 Correct 532 ms 616448 KB Output is correct
5 Correct 524 ms 616020 KB Output is correct
6 Correct 545 ms 616268 KB Output is correct
7 Correct 543 ms 616472 KB Output is correct
8 Correct 523 ms 616076 KB Output is correct
9 Correct 512 ms 616012 KB Output is correct
10 Correct 503 ms 616184 KB Output is correct
11 Correct 620 ms 616204 KB Output is correct
12 Correct 767 ms 616488 KB Output is correct
13 Correct 609 ms 616280 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 492212 KB Output is correct
2 Correct 617 ms 616772 KB Output is correct
3 Correct 553 ms 616928 KB Output is correct
4 Correct 532 ms 616448 KB Output is correct
5 Correct 524 ms 616020 KB Output is correct
6 Correct 545 ms 616268 KB Output is correct
7 Correct 543 ms 616472 KB Output is correct
8 Correct 523 ms 616076 KB Output is correct
9 Correct 512 ms 616012 KB Output is correct
10 Correct 503 ms 616184 KB Output is correct
11 Correct 620 ms 616204 KB Output is correct
12 Correct 767 ms 616488 KB Output is correct
13 Correct 609 ms 616280 KB Output is correct
14 Correct 179 ms 492308 KB Output is correct
15 Correct 544 ms 616544 KB Output is correct
16 Correct 566 ms 616812 KB Output is correct
17 Correct 558 ms 616140 KB Output is correct
18 Correct 539 ms 616292 KB Output is correct
19 Correct 577 ms 616544 KB Output is correct
20 Correct 543 ms 615956 KB Output is correct
21 Correct 560 ms 616132 KB Output is correct
22 Correct 532 ms 616248 KB Output is correct
23 Correct 698 ms 616520 KB Output is correct
24 Correct 762 ms 616408 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 492212 KB Output is correct
2 Correct 617 ms 616772 KB Output is correct
3 Correct 553 ms 616928 KB Output is correct
4 Correct 532 ms 616448 KB Output is correct
5 Correct 524 ms 616020 KB Output is correct
6 Correct 545 ms 616268 KB Output is correct
7 Correct 543 ms 616472 KB Output is correct
8 Correct 523 ms 616076 KB Output is correct
9 Correct 512 ms 616012 KB Output is correct
10 Correct 503 ms 616184 KB Output is correct
11 Correct 620 ms 616204 KB Output is correct
12 Correct 767 ms 616488 KB Output is correct
13 Correct 609 ms 616280 KB Output is correct
14 Correct 179 ms 492308 KB Output is correct
15 Correct 544 ms 616544 KB Output is correct
16 Correct 566 ms 616812 KB Output is correct
17 Correct 558 ms 616140 KB Output is correct
18 Correct 539 ms 616292 KB Output is correct
19 Correct 577 ms 616544 KB Output is correct
20 Correct 543 ms 615956 KB Output is correct
21 Correct 560 ms 616132 KB Output is correct
22 Correct 532 ms 616248 KB Output is correct
23 Correct 698 ms 616520 KB Output is correct
24 Correct 762 ms 616408 KB Output is correct
25 Correct 503 ms 615504 KB Output is correct
26 Correct 565 ms 616908 KB Output is correct
27 Correct 588 ms 616208 KB Output is correct
28 Correct 547 ms 616156 KB Output is correct
29 Correct 565 ms 616648 KB Output is correct
30 Correct 607 ms 616380 KB Output is correct
31 Correct 564 ms 616560 KB Output is correct
32 Correct 808 ms 616132 KB Output is correct
33 Correct 658 ms 616396 KB Output is correct
34 Correct 1228 ms 616184 KB Output is correct
35 Correct 691 ms 616452 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 492468 KB Output is correct
2 Runtime error 4461 ms 1158624 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -