oj.uz

Submission #439953

# Submission time Handle Problem Language Result Execution time Memory
439953 2021-07-01T09:45:32 Z dacin21 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 5705 ms 162560 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 = 1000;
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;

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;
	}

	// 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};
	    }
	}
}

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;
        }
    };
    for(int it=0; it<BLOCK; ++it){
        do_single_step();
    }
    assert(u == n || s >= BLOCK);
    while(u != n && s < MAX_SKILL){
        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();
    }
    s += win_gain[u];
    return s;
}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:65:45: 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]
   65 |             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 2 ms 1100 KB Output is correct
4 Correct 37 ms 20416 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 37 ms 20420 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 708 KB Output is correct
2 Correct 784 ms 162324 KB Output is correct
3 Correct 806 ms 162340 KB Output is correct
4 Correct 765 ms 162340 KB Output is correct
5 Correct 588 ms 162340 KB Output is correct
6 Correct 748 ms 162372 KB Output is correct
7 Correct 740 ms 162332 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 716 KB Output is correct
2 Correct 289 ms 21184 KB Output is correct
3 Correct 272 ms 21192 KB Output is correct
4 Correct 383 ms 21280 KB Output is correct
5 Correct 371 ms 21184 KB Output is correct
6 Correct 395 ms 21188 KB Output is correct
7 Correct 399 ms 21196 KB Output is correct
8 Correct 401 ms 21184 KB Output is correct
9 Correct 276 ms 21188 KB Output is correct
10 Correct 396 ms 21200 KB Output is correct
11 Correct 904 ms 21176 KB Output is correct
12 Correct 1179 ms 21188 KB Output is correct
13 Correct 540 ms 21188 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 716 KB Output is correct
2 Correct 289 ms 21184 KB Output is correct
3 Correct 272 ms 21192 KB Output is correct
4 Correct 383 ms 21280 KB Output is correct
5 Correct 371 ms 21184 KB Output is correct
6 Correct 395 ms 21188 KB Output is correct
7 Correct 399 ms 21196 KB Output is correct
8 Correct 401 ms 21184 KB Output is correct
9 Correct 276 ms 21188 KB Output is correct
10 Correct 396 ms 21200 KB Output is correct
11 Correct 904 ms 21176 KB Output is correct
12 Correct 1179 ms 21188 KB Output is correct
13 Correct 540 ms 21188 KB Output is correct
14 Correct 7 ms 716 KB Output is correct
15 Correct 274 ms 21192 KB Output is correct
16 Correct 289 ms 21188 KB Output is correct
17 Correct 397 ms 21312 KB Output is correct
18 Correct 355 ms 21188 KB Output is correct
19 Correct 402 ms 21196 KB Output is correct
20 Correct 338 ms 21188 KB Output is correct
21 Correct 370 ms 21192 KB Output is correct
22 Correct 497 ms 21300 KB Output is correct
23 Correct 984 ms 21184 KB Output is correct
24 Correct 1183 ms 21196 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 716 KB Output is correct
2 Correct 289 ms 21184 KB Output is correct
3 Correct 272 ms 21192 KB Output is correct
4 Correct 383 ms 21280 KB Output is correct
5 Correct 371 ms 21184 KB Output is correct
6 Correct 395 ms 21188 KB Output is correct
7 Correct 399 ms 21196 KB Output is correct
8 Correct 401 ms 21184 KB Output is correct
9 Correct 276 ms 21188 KB Output is correct
10 Correct 396 ms 21200 KB Output is correct
11 Correct 904 ms 21176 KB Output is correct
12 Correct 1179 ms 21188 KB Output is correct
13 Correct 540 ms 21188 KB Output is correct
14 Correct 7 ms 716 KB Output is correct
15 Correct 274 ms 21192 KB Output is correct
16 Correct 289 ms 21188 KB Output is correct
17 Correct 397 ms 21312 KB Output is correct
18 Correct 355 ms 21188 KB Output is correct
19 Correct 402 ms 21196 KB Output is correct
20 Correct 338 ms 21188 KB Output is correct
21 Correct 370 ms 21192 KB Output is correct
22 Correct 497 ms 21300 KB Output is correct
23 Correct 984 ms 21184 KB Output is correct
24 Correct 1183 ms 21196 KB Output is correct
25 Correct 42 ms 20428 KB Output is correct
26 Correct 276 ms 21188 KB Output is correct
27 Correct 272 ms 21196 KB Output is correct
28 Correct 270 ms 21188 KB Output is correct
29 Correct 271 ms 21196 KB Output is correct
30 Correct 406 ms 21196 KB Output is correct
31 Correct 480 ms 21184 KB Output is correct
32 Correct 1514 ms 21188 KB Output is correct
33 Correct 368 ms 21196 KB Output is correct
34 Correct 1257 ms 21188 KB Output is correct
35 Correct 746 ms 21192 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 708 KB Output is correct
2 Correct 784 ms 162324 KB Output is correct
3 Correct 806 ms 162340 KB Output is correct
4 Correct 765 ms 162340 KB Output is correct
5 Correct 588 ms 162340 KB Output is correct
6 Correct 748 ms 162372 KB Output is correct
7 Correct 740 ms 162332 KB Output is correct
8 Correct 7 ms 716 KB Output is correct
9 Correct 289 ms 21184 KB Output is correct
10 Correct 272 ms 21192 KB Output is correct
11 Correct 383 ms 21280 KB Output is correct
12 Correct 371 ms 21184 KB Output is correct
13 Correct 395 ms 21188 KB Output is correct
14 Correct 399 ms 21196 KB Output is correct
15 Correct 401 ms 21184 KB Output is correct
16 Correct 276 ms 21188 KB Output is correct
17 Correct 396 ms 21200 KB Output is correct
18 Correct 904 ms 21176 KB Output is correct
19 Correct 1179 ms 21188 KB Output is correct
20 Correct 540 ms 21188 KB Output is correct
21 Correct 7 ms 716 KB Output is correct
22 Correct 274 ms 21192 KB Output is correct
23 Correct 289 ms 21188 KB Output is correct
24 Correct 397 ms 21312 KB Output is correct
25 Correct 355 ms 21188 KB Output is correct
26 Correct 402 ms 21196 KB Output is correct
27 Correct 338 ms 21188 KB Output is correct
28 Correct 370 ms 21192 KB Output is correct
29 Correct 497 ms 21300 KB Output is correct
30 Correct 984 ms 21184 KB Output is correct
31 Correct 1183 ms 21196 KB Output is correct
32 Correct 42 ms 20428 KB Output is correct
33 Correct 276 ms 21188 KB Output is correct
34 Correct 272 ms 21196 KB Output is correct
35 Correct 270 ms 21188 KB Output is correct
36 Correct 271 ms 21196 KB Output is correct
37 Correct 406 ms 21196 KB Output is correct
38 Correct 480 ms 21184 KB Output is correct
39 Correct 1514 ms 21188 KB Output is correct
40 Correct 368 ms 21196 KB Output is correct
41 Correct 1257 ms 21188 KB Output is correct
42 Correct 746 ms 21192 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 7 ms 588 KB Output is correct
45 Correct 598 ms 162340 KB Output is correct
46 Correct 556 ms 162372 KB Output is correct
47 Correct 578 ms 162376 KB Output is correct
48 Correct 559 ms 162340 KB Output is correct
49 Correct 599 ms 162332 KB Output is correct
50 Correct 818 ms 162280 KB Output is correct
51 Correct 571 ms 162372 KB Output is correct
52 Correct 782 ms 162352 KB Output is correct
53 Correct 5705 ms 162272 KB Output is correct
54 Correct 1200 ms 162500 KB Output is correct
55 Correct 2363 ms 162512 KB Output is correct
56 Correct 2958 ms 162556 KB Output is correct
57 Correct 1902 ms 162560 KB Output is correct
58 Correct 1501 ms 162500 KB Output is correct
59 Correct 1549 ms 162500 KB Output is correct
60 Correct 2021 ms 162372 KB Output is correct
61 Correct 1801 ms 162372 KB Output is correct