Submission #152531

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
152531	2019-09-08T09:21:55 Z	dolphingarlic	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	887 ms	235884 KB

brunhilda

#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

int dp[20000003], p[100001], max_divide[20000003], to[20000003];

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);

    int n, q;
    cin >> n >> q;
    FOR(i, 0, n) cin >> p[i];
    FOR(i, 0, n) for (int j = p[i]; j <= 20000001; j += p[i]) max_divide[j] = p[i];

    int mn = 20000000;
    for (int i = 20000000; i > 0; i--) {
        mn = min(mn, i + 1 - max_divide[i + 1]);
        to[i] = mn;
    }

    FOR(i, 1, 20000001) if (to[i] == i) dp[i] = 987654321;
    else dp[i] = dp[to[i]] + 1;

    FOR(i, 0, q) {
        int x;
        cin >> x;
        if (dp[x] >= 987654321)
            cout << "oo\n";
        else
            cout << dp[x] << '\n';
    }
    return 0;
}

Compilation message

brunhilda.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	240 ms	235128 KB	Output is correct
2	Correct	296 ms	235272 KB	Output is correct
3	Correct	259 ms	235128 KB	Output is correct
4	Correct	286 ms	235116 KB	Output is correct
5	Correct	300 ms	235204 KB	Output is correct
6	Correct	273 ms	235180 KB	Output is correct
7	Correct	280 ms	235216 KB	Output is correct
8	Correct	274 ms	235100 KB	Output is correct
9	Correct	321 ms	235100 KB	Output is correct
10	Correct	383 ms	235224 KB	Output is correct
11	Correct	388 ms	235208 KB	Output is correct
12	Correct	242 ms	235140 KB	Output is correct
13	Correct	650 ms	235228 KB	Output is correct
14	Correct	633 ms	235344 KB	Output is correct
15	Correct	329 ms	235128 KB	Output is correct
16	Correct	312 ms	235164 KB	Output is correct
17	Correct	307 ms	235212 KB	Output is correct
18	Correct	251 ms	235228 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	285 ms	235276 KB	Output is correct
2	Correct	311 ms	235512 KB	Output is correct
3	Correct	782 ms	235452 KB	Output is correct
4	Correct	347 ms	235340 KB	Output is correct
5	Correct	552 ms	235388 KB	Output is correct
6	Correct	297 ms	235220 KB	Output is correct
7	Correct	297 ms	235256 KB	Output is correct
8	Correct	343 ms	235256 KB	Output is correct
9	Correct	632 ms	235556 KB	Output is correct
10	Correct	780 ms	235484 KB	Output is correct
11	Correct	767 ms	235384 KB	Output is correct
12	Correct	444 ms	235128 KB	Output is correct
13	Correct	269 ms	235256 KB	Output is correct
14	Correct	349 ms	235256 KB	Output is correct
15	Correct	630 ms	235384 KB	Output is correct
16	Correct	329 ms	235484 KB	Output is correct
17	Correct	670 ms	235264 KB	Output is correct
18	Correct	636 ms	235640 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	708 ms	235544 KB	Output is correct
2	Correct	829 ms	235548 KB	Output is correct
3	Correct	797 ms	235732 KB	Output is correct
4	Correct	477 ms	235484 KB	Output is correct
5	Correct	365 ms	235768 KB	Output is correct
6	Correct	648 ms	235640 KB	Output is correct
7	Correct	573 ms	235616 KB	Output is correct
8	Correct	627 ms	235512 KB	Output is correct
9	Correct	628 ms	235640 KB	Output is correct
10	Correct	532 ms	235348 KB	Output is correct
11	Correct	479 ms	235388 KB	Output is correct
12	Correct	608 ms	235236 KB	Output is correct
13	Correct	761 ms	235512 KB	Output is correct
14	Correct	420 ms	235700 KB	Output is correct
15	Correct	621 ms	235256 KB	Output is correct
16	Correct	715 ms	235372 KB	Output is correct
17	Correct	657 ms	235396 KB	Output is correct
18	Correct	804 ms	235512 KB	Output is correct
19	Correct	279 ms	235256 KB	Output is correct
20	Correct	800 ms	235484 KB	Output is correct
21	Correct	514 ms	235768 KB	Output is correct
22	Correct	811 ms	235884 KB	Output is correct
23	Correct	373 ms	235592 KB	Output is correct
24	Correct	302 ms	235600 KB	Output is correct
25	Correct	535 ms	235436 KB	Output is correct
26	Correct	478 ms	235552 KB	Output is correct
27	Correct	887 ms	235676 KB	Output is correct
28	Correct	306 ms	235472 KB	Output is correct
29	Correct	812 ms	235696 KB	Output is correct
30	Correct	706 ms	235604 KB	Output is correct
31	Correct	357 ms	235384 KB	Output is correct
32	Correct	395 ms	235512 KB	Output is correct
33	Correct	266 ms	235512 KB	Output is correct
34	Correct	618 ms	235740 KB	Output is correct
35	Correct	328 ms	235488 KB	Output is correct
36	Correct	762 ms	235768 KB	Output is correct
37	Correct	358 ms	235768 KB	Output is correct
38	Correct	649 ms	235392 KB	Output is correct
39	Correct	326 ms	235548 KB	Output is correct
40	Correct	553 ms	235512 KB	Output is correct
41	Correct	507 ms	235600 KB	Output is correct
42	Correct	741 ms	235616 KB	Output is correct