oj.uz

Submission #242160

# Submission time Handle Problem Language Result Execution time Memory
242160 2020-06-27T03:18:49 Z thecodingwizard Brunhilda’s Birthday (BOI13_brunhilda) C++11
100 / 100
 586 ms 44792 KB 
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second

int A[100000]; 
int dp[10000001]; 
set<ii> transitions;

int main() {
    int m, q; cin >> m >> q;
    for (int i = 0; i < m; i++) cin >> A[i];
    for (int i = 0; i < 10000001; i++) dp[i] = -1;
    dp[0] = 0;

    int nxtStart = 0, nxtVal = 0;
    for (int i = 0; i < m; i++) {
        nxtVal = max(nxtVal, A[i]);

        transitions.insert({A[i],A[i]});
    }

    while (nxtStart != -1) {
        int begin = nxtStart, end = begin + nxtVal;
        nxtStart = -1;
        nxtVal = 0;

        end = min(end, 10000001);

        while (!transitions.empty() && transitions.begin()->f < end) {
            int x = transitions.begin()->s;
            transitions.erase(transitions.begin());
            int i = (end-1)/x*x;
            if (nxtStart+nxtVal < i + x) {
                nxtStart = i;
                nxtVal = x;
            }
            int nxt = (end-1)/x*x+x;
            if (nxt <= 10000000) transitions.insert({nxt,x});
        }

        for (int i = begin + 1; i < end; i++) {
            if (dp[i] == -1) dp[i] = dp[begin]+1;
        }
    }

    for (int i = 0; i < q; i++) {
        int x; cin >> x;
        if (dp[x] == -1) cout << "oo" << "\n";
        else cout << dp[x] << "\n";
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39424 KB Output is correct
2 Correct 154 ms 39500 KB Output is correct
3 Correct 29 ms 39424 KB Output is correct
4 Correct 87 ms 39416 KB Output is correct
5 Correct 195 ms 39424 KB Output is correct
6 Correct 29 ms 39424 KB Output is correct
7 Correct 28 ms 39424 KB Output is correct
8 Correct 42 ms 39424 KB Output is correct
9 Correct 320 ms 39424 KB Output is correct
10 Correct 249 ms 39532 KB Output is correct
11 Correct 249 ms 39424 KB Output is correct
12 Correct 88 ms 39544 KB Output is correct
13 Correct 240 ms 39552 KB Output is correct
14 Correct 254 ms 39672 KB Output is correct
15 Correct 134 ms 39544 KB Output is correct
16 Correct 160 ms 39416 KB Output is correct
17 Correct 201 ms 39424 KB Output is correct
18 Correct 85 ms 39424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 40064 KB Output is correct
2 Correct 106 ms 44024 KB Output is correct
3 Correct 187 ms 43040 KB Output is correct
4 Correct 96 ms 39660 KB Output is correct
5 Correct 144 ms 42156 KB Output is correct
6 Correct 62 ms 39672 KB Output is correct
7 Correct 63 ms 40064 KB Output is correct
8 Correct 96 ms 39552 KB Output is correct
9 Correct 197 ms 43128 KB Output is correct
10 Correct 197 ms 43000 KB Output is correct
11 Correct 222 ms 41464 KB Output is correct
12 Correct 115 ms 39552 KB Output is correct
13 Correct 45 ms 39680 KB Output is correct
14 Correct 92 ms 39552 KB Output is correct
15 Correct 169 ms 41592 KB Output is correct
16 Correct 110 ms 44028 KB Output is correct
17 Correct 209 ms 39672 KB Output is correct
18 Correct 159 ms 44608 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 42232 KB Output is correct
2 Correct 311 ms 42204 KB Output is correct
3 Correct 372 ms 42232 KB Output is correct
4 Correct 330 ms 40056 KB Output is correct
5 Correct 384 ms 44664 KB Output is correct
6 Correct 404 ms 40212 KB Output is correct
7 Correct 333 ms 44664 KB Output is correct
8 Correct 267 ms 42104 KB Output is correct
9 Correct 266 ms 42104 KB Output is correct
10 Correct 183 ms 39800 KB Output is correct
11 Correct 179 ms 39828 KB Output is correct
12 Correct 212 ms 39928 KB Output is correct
13 Correct 450 ms 41336 KB Output is correct
14 Correct 586 ms 40060 KB Output is correct
15 Correct 238 ms 39800 KB Output is correct
16 Correct 284 ms 39928 KB Output is correct
17 Correct 215 ms 41792 KB Output is correct
18 Correct 300 ms 42360 KB Output is correct
19 Correct 105 ms 39800 KB Output is correct
20 Correct 371 ms 42232 KB Output is correct
21 Correct 471 ms 40056 KB Output is correct
22 Correct 498 ms 44792 KB Output is correct
23 Correct 356 ms 41208 KB Output is correct
24 Correct 300 ms 39928 KB Output is correct
25 Correct 389 ms 39928 KB Output is correct
26 Correct 321 ms 39928 KB Output is correct
27 Correct 401 ms 44664 KB Output is correct
28 Correct 312 ms 39800 KB Output is correct
29 Correct 527 ms 44792 KB Output is correct
30 Correct 500 ms 43408 KB Output is correct
31 Correct 289 ms 39928 KB Output is correct
32 Correct 330 ms 40184 KB Output is correct
33 Correct 278 ms 39800 KB Output is correct
34 Correct 331 ms 44720 KB Output is correct
35 Correct 314 ms 39800 KB Output is correct
36 Correct 458 ms 44280 KB Output is correct
37 Correct 387 ms 44792 KB Output is correct
38 Correct 410 ms 40184 KB Output is correct
39 Correct 323 ms 39800 KB Output is correct
40 Correct 376 ms 40184 KB Output is correct
41 Correct 264 ms 44664 KB Output is correct
42 Correct 438 ms 40116 KB Output is correct