oj.uz

Submission #439957

# Submission time Handle Problem Language Result Execution time Memory
439957 2021-07-01T09:51:33 Z dacin21 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3386 ms 293996 KB 
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") // codeforces

#undef _GLIBCXX_DEBUG

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using ll = int64_t;

const int BLOCK_1 = 500;
const int BLOCK_2 = 50000;
const int MAX_SKILL = 1.01e7;
const int U = 20;
const int inf = 1e9;

int n;
struct Link{
    int to;
    int gain;
};
struct Node{
    Link win, loss;
    int thresh;
};
struct Jump{
    int to;
    int max_valid;
    ll gain;
};
vector<ll> win_gain;
vector<Node> g;
vector<vector<Jump> > jumps_1;
vector<vector<Jump> > jumps_2;

void init(int n_, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
	n = n_;
	g.assign(n+1, Node{});
	for(int i=0; i<n; ++i){
        g[i] = Node{Link{w[i], s[i]}, Link{l[i], p[i]}, s[i]};
	}
	g[n] = Node{Link{n, 0}, Link{n, 0}, 0};

	// compute win once we hit 1e7
	win_gain.assign(n+1, 0);
	for(int i=n-1; i>=0; --i){
        win_gain[i] = win_gain[g[i].win.to] + g[i].win.gain;
	}

	auto compute_table = [&](auto &jumps, int BLOCK){
        // assume we take BLOCK steps
        // then build jump table
        jumps.resize(U+1, vector<Jump>(n+1));
        for(int i=0; i<=n; ++i){
            if(g[i].thresh <= BLOCK){
                jumps[0][i] = Jump{g[i].win.to, inf, g[i].win.gain};
            } else {
                jumps[0][i] = Jump{g[i].loss.to, g[i].thresh-1, g[i].loss.gain};
            }
        }
        jumps[0][n].max_valid = 0;
        for(int i=1; i<=U; ++i){
            for(int j=0; j<=n; ++j){
                auto &e = jumps[i-1][j];
                const int k = e.to;
                auto const&f = jumps[i-1][k];
                jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
            }
        }
	};
	compute_table(jumps_1, BLOCK_1);
	compute_table(jumps_2, BLOCK_2);
}

long long simulate(int x, int z) {
    int u = x;
    ll s = z;
    auto do_single_step = [&](){
        if(s >= g[u].thresh){
            s += g[u].win.gain;
            u = g[u].win.to;
        } else {
            s += g[u].loss.gain;
            u = g[u].loss.to;
        }
    };
    auto run_with_jumps = [&](auto const&jumps, int const SKILL_CAP){
        while(u != n && s < SKILL_CAP){
            int i = 0;
            while(i >= 0){
                auto &e = jumps[i][u];
                if(s < e.max_valid){
                    s += e.gain;
                    u = e.to;
                    i = min(i+1, U);
                } else --i;
            }
            do_single_step();
        }
    };
    for(int it=0; it<BLOCK_1; ++it){
        do_single_step();
    }
    assert(u == n || s >= BLOCK_1);
    run_with_jumps(jumps_1, BLOCK_2);
    run_with_jumps(jumps_2, MAX_SKILL);
    s += win_gain[u];
    return s;
}

Compilation message

dungeons.cpp: In instantiation of 'init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)::<lambda(auto:23&, int)> [with auto:23 = std::vector<std::vector<Jump> >]':
dungeons.cpp:72:32:   required from here
dungeons.cpp:68:29: warning: narrowing conversion of '(long int)std::max<long int>(-1, (* & std::min<long int>(((long int)e.Jump::max_valid), (((ll)((int)f.Jump::max_valid)) - e.Jump::gain))))' from 'long int' to 'int' [-Wnarrowing]
   68 |                 jumps[i][j] = Jump{f.to, max<ll>(-1, min<ll>(e.max_valid, f.max_valid-e.gain)), e.gain+f.gain};
      |                 ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 1740 KB Output is correct
4 Correct 48 ms 36880 KB Output is correct
5 Correct 3 ms 1740 KB Output is correct
6 Correct 47 ms 36944 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 745 ms 293808 KB Output is correct
3 Correct 752 ms 293816 KB Output is correct
4 Correct 781 ms 293864 KB Output is correct
5 Correct 588 ms 293856 KB Output is correct
6 Correct 768 ms 293792 KB Output is correct
7 Correct 1026 ms 293804 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 185 ms 37688 KB Output is correct
3 Correct 186 ms 37680 KB Output is correct
4 Correct 314 ms 37688 KB Output is correct
5 Correct 286 ms 37684 KB Output is correct
6 Correct 309 ms 37684 KB Output is correct
7 Correct 326 ms 37688 KB Output is correct
8 Correct 319 ms 37684 KB Output is correct
9 Correct 177 ms 37684 KB Output is correct
10 Correct 308 ms 37684 KB Output is correct
11 Correct 595 ms 37736 KB Output is correct
12 Correct 847 ms 37728 KB Output is correct
13 Correct 412 ms 37676 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 185 ms 37688 KB Output is correct
3 Correct 186 ms 37680 KB Output is correct
4 Correct 314 ms 37688 KB Output is correct
5 Correct 286 ms 37684 KB Output is correct
6 Correct 309 ms 37684 KB Output is correct
7 Correct 326 ms 37688 KB Output is correct
8 Correct 319 ms 37684 KB Output is correct
9 Correct 177 ms 37684 KB Output is correct
10 Correct 308 ms 37684 KB Output is correct
11 Correct 595 ms 37736 KB Output is correct
12 Correct 847 ms 37728 KB Output is correct
13 Correct 412 ms 37676 KB Output is correct
14 Correct 5 ms 972 KB Output is correct
15 Correct 224 ms 37656 KB Output is correct
16 Correct 186 ms 37680 KB Output is correct
17 Correct 317 ms 37684 KB Output is correct
18 Correct 314 ms 37684 KB Output is correct
19 Correct 350 ms 37692 KB Output is correct
20 Correct 277 ms 37692 KB Output is correct
21 Correct 254 ms 37612 KB Output is correct
22 Correct 362 ms 37680 KB Output is correct
23 Correct 635 ms 37688 KB Output is correct
24 Correct 806 ms 37688 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 185 ms 37688 KB Output is correct
3 Correct 186 ms 37680 KB Output is correct
4 Correct 314 ms 37688 KB Output is correct
5 Correct 286 ms 37684 KB Output is correct
6 Correct 309 ms 37684 KB Output is correct
7 Correct 326 ms 37688 KB Output is correct
8 Correct 319 ms 37684 KB Output is correct
9 Correct 177 ms 37684 KB Output is correct
10 Correct 308 ms 37684 KB Output is correct
11 Correct 595 ms 37736 KB Output is correct
12 Correct 847 ms 37728 KB Output is correct
13 Correct 412 ms 37676 KB Output is correct
14 Correct 5 ms 972 KB Output is correct
15 Correct 224 ms 37656 KB Output is correct
16 Correct 186 ms 37680 KB Output is correct
17 Correct 317 ms 37684 KB Output is correct
18 Correct 314 ms 37684 KB Output is correct
19 Correct 350 ms 37692 KB Output is correct
20 Correct 277 ms 37692 KB Output is correct
21 Correct 254 ms 37612 KB Output is correct
22 Correct 362 ms 37680 KB Output is correct
23 Correct 635 ms 37688 KB Output is correct
24 Correct 806 ms 37688 KB Output is correct
25 Correct 56 ms 36916 KB Output is correct
26 Correct 192 ms 37680 KB Output is correct
27 Correct 179 ms 37680 KB Output is correct
28 Correct 184 ms 37688 KB Output is correct
29 Correct 209 ms 37732 KB Output is correct
30 Correct 332 ms 37660 KB Output is correct
31 Correct 388 ms 37680 KB Output is correct
32 Correct 898 ms 37680 KB Output is correct
33 Correct 252 ms 37684 KB Output is correct
34 Correct 1455 ms 37684 KB Output is correct
35 Correct 610 ms 37692 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 972 KB Output is correct
2 Correct 745 ms 293808 KB Output is correct
3 Correct 752 ms 293816 KB Output is correct
4 Correct 781 ms 293864 KB Output is correct
5 Correct 588 ms 293856 KB Output is correct
6 Correct 768 ms 293792 KB Output is correct
7 Correct 1026 ms 293804 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 185 ms 37688 KB Output is correct
10 Correct 186 ms 37680 KB Output is correct
11 Correct 314 ms 37688 KB Output is correct
12 Correct 286 ms 37684 KB Output is correct
13 Correct 309 ms 37684 KB Output is correct
14 Correct 326 ms 37688 KB Output is correct
15 Correct 319 ms 37684 KB Output is correct
16 Correct 177 ms 37684 KB Output is correct
17 Correct 308 ms 37684 KB Output is correct
18 Correct 595 ms 37736 KB Output is correct
19 Correct 847 ms 37728 KB Output is correct
20 Correct 412 ms 37676 KB Output is correct
21 Correct 5 ms 972 KB Output is correct
22 Correct 224 ms 37656 KB Output is correct
23 Correct 186 ms 37680 KB Output is correct
24 Correct 317 ms 37684 KB Output is correct
25 Correct 314 ms 37684 KB Output is correct
26 Correct 350 ms 37692 KB Output is correct
27 Correct 277 ms 37692 KB Output is correct
28 Correct 254 ms 37612 KB Output is correct
29 Correct 362 ms 37680 KB Output is correct
30 Correct 635 ms 37688 KB Output is correct
31 Correct 806 ms 37688 KB Output is correct
32 Correct 56 ms 36916 KB Output is correct
33 Correct 192 ms 37680 KB Output is correct
34 Correct 179 ms 37680 KB Output is correct
35 Correct 184 ms 37688 KB Output is correct
36 Correct 209 ms 37732 KB Output is correct
37 Correct 332 ms 37660 KB Output is correct
38 Correct 388 ms 37680 KB Output is correct
39 Correct 898 ms 37680 KB Output is correct
40 Correct 252 ms 37684 KB Output is correct
41 Correct 1455 ms 37684 KB Output is correct
42 Correct 610 ms 37692 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 5 ms 1036 KB Output is correct
45 Correct 680 ms 293892 KB Output is correct
46 Correct 538 ms 293840 KB Output is correct
47 Correct 589 ms 293904 KB Output is correct
48 Correct 610 ms 293812 KB Output is correct
49 Correct 648 ms 293860 KB Output is correct
50 Correct 829 ms 293852 KB Output is correct
51 Correct 561 ms 293996 KB Output is correct
52 Correct 850 ms 293888 KB Output is correct
53 Correct 3386 ms 293980 KB Output is correct
54 Correct 921 ms 293864 KB Output is correct
55 Correct 2760 ms 293936 KB Output is correct
56 Correct 2626 ms 293852 KB Output is correct
57 Correct 2141 ms 293840 KB Output is correct
58 Correct 1753 ms 293968 KB Output is correct
59 Correct 1631 ms 293920 KB Output is correct
60 Correct 1763 ms 293824 KB Output is correct
61 Correct 1810 ms 293968 KB Output is correct