oj.uz

Submission #242159

# Submission time Handle Problem Language Result Execution time Memory
242159 2020-06-27T03:17:37 Z thecodingwizard Brunhilda’s Birthday (BOI13_brunhilda) C++11
48.0952 / 100
 515 ms 45432 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, i = transitions.begin()->f;
            transitions.erase(transitions.begin());
            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
4.44444444444 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 39424 KB Output isn't correct
2 Incorrect 159 ms 39424 KB Output isn't correct
3 Incorrect 24 ms 39424 KB Output isn't correct
4 Incorrect 92 ms 39544 KB Output isn't correct
5 Correct 72 ms 39424 KB Output is correct
6 Incorrect 26 ms 39424 KB Output isn't correct
7 Incorrect 25 ms 39424 KB Output isn't correct
8 Incorrect 24 ms 39424 KB Output isn't correct
9 Incorrect 24 ms 39424 KB Output isn't correct
10 Incorrect 27 ms 39424 KB Output isn't correct
11 Incorrect 26 ms 39424 KB Output isn't correct
12 Correct 87 ms 39424 KB Output is correct
13 Correct 245 ms 39552 KB Output is correct
14 Correct 261 ms 39672 KB Output is correct
15 Incorrect 156 ms 39424 KB Output isn't correct
16 Incorrect 165 ms 39544 KB Output isn't correct
17 Incorrect 56 ms 39424 KB Output isn't correct
18 Incorrect 91 ms 39424 KB Output isn't correct

Subtask #2
12.2222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 40064 KB Output is correct
2 Correct 109 ms 44152 KB Output is correct
3 Incorrect 91 ms 43000 KB Output isn't correct
4 Correct 94 ms 39668 KB Output is correct
5 Correct 153 ms 42104 KB Output is correct
6 Correct 61 ms 39544 KB Output is correct
7 Correct 66 ms 40056 KB Output is correct
8 Incorrect 95 ms 39552 KB Output isn't correct
9 Correct 194 ms 43128 KB Output is correct
10 Incorrect 89 ms 43004 KB Output isn't correct
11 Incorrect 244 ms 41592 KB Output isn't correct
12 Incorrect 116 ms 39552 KB Output isn't correct
13 Correct 45 ms 39552 KB Output is correct
14 Correct 97 ms 39680 KB Output is correct
15 Correct 179 ms 41720 KB Output is correct
16 Correct 110 ms 44152 KB Output is correct
17 Incorrect 26 ms 39544 KB Output isn't correct
18 Incorrect 123 ms 44536 KB Output isn't correct

Subtask #3
31.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 42232 KB Output is correct
2 Correct 301 ms 42244 KB Output is correct
3 Correct 372 ms 42488 KB Output is correct
4 Incorrect 328 ms 40440 KB Output isn't correct
5 Correct 396 ms 44664 KB Output is correct
6 Incorrect 407 ms 40696 KB Output isn't correct
7 Correct 323 ms 44920 KB Output is correct
8 Correct 275 ms 42232 KB Output is correct
9 Correct 280 ms 42232 KB Output is correct
10 Incorrect 188 ms 39928 KB Output isn't correct
11 Incorrect 182 ms 39928 KB Output isn't correct
12 Incorrect 220 ms 39928 KB Output isn't correct
13 Incorrect 409 ms 41848 KB Output isn't correct
14 Incorrect 260 ms 40568 KB Output isn't correct
15 Incorrect 239 ms 39928 KB Output isn't correct
16 Incorrect 280 ms 40056 KB Output isn't correct
17 Correct 216 ms 41720 KB Output is correct
18 Correct 301 ms 42232 KB Output is correct
19 Correct 104 ms 39800 KB Output is correct
20 Correct 378 ms 42488 KB Output is correct
21 Incorrect 259 ms 40568 KB Output isn't correct
22 Correct 492 ms 45432 KB Output is correct
23 Correct 382 ms 41236 KB Output is correct
24 Incorrect 295 ms 40056 KB Output isn't correct
25 Incorrect 382 ms 40696 KB Output isn't correct
26 Incorrect 325 ms 40440 KB Output isn't correct
27 Correct 416 ms 44972 KB Output is correct
28 Incorrect 270 ms 39800 KB Output isn't correct
29 Correct 515 ms 45432 KB Output is correct
30 Correct 479 ms 43896 KB Output is correct
31 Correct 287 ms 40056 KB Output is correct
32 Incorrect 337 ms 40188 KB Output isn't correct
33 Incorrect 288 ms 39800 KB Output isn't correct
34 Correct 320 ms 44920 KB Output is correct
35 Incorrect 315 ms 39928 KB Output isn't correct
36 Correct 481 ms 44792 KB Output is correct
37 Correct 389 ms 44920 KB Output is correct
38 Incorrect 407 ms 40696 KB Output isn't correct
39 Incorrect 317 ms 39928 KB Output isn't correct
40 Correct 377 ms 40696 KB Output is correct
41 Correct 261 ms 44920 KB Output is correct
42 Incorrect 457 ms 40824 KB Output isn't correct