답안 #152530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152530	2019-09-08T09:21:16 Z	dolphingarlic	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	97.7778 / 100	885 ms	235864 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] >= INT_MAX)
            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

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	259 ms	235356 KB	Output isn't correct
2	Correct	319 ms	235256 KB	Output is correct
3	Correct	264 ms	235256 KB	Output is correct
4	Correct	246 ms	235224 KB	Output is correct
5	Correct	276 ms	235128 KB	Output is correct
6	Incorrect	240 ms	235280 KB	Output isn't correct
7	Correct	290 ms	235256 KB	Output is correct
8	Correct	280 ms	235324 KB	Output is correct
9	Correct	317 ms	235120 KB	Output is correct
10	Correct	374 ms	235132 KB	Output is correct
11	Correct	352 ms	235220 KB	Output is correct
12	Correct	241 ms	235128 KB	Output is correct
13	Correct	633 ms	235168 KB	Output is correct
14	Correct	635 ms	235224 KB	Output is correct
15	Correct	320 ms	235128 KB	Output is correct
16	Correct	297 ms	235308 KB	Output is correct
17	Correct	304 ms	235256 KB	Output is correct
18	Correct	281 ms	235256 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	299 ms	235244 KB	Output is correct
2	Correct	354 ms	235620 KB	Output is correct
3	Correct	778 ms	235544 KB	Output is correct
4	Correct	347 ms	235256 KB	Output is correct
5	Correct	539 ms	235512 KB	Output is correct
6	Correct	299 ms	235240 KB	Output is correct
7	Correct	319 ms	235256 KB	Output is correct
8	Correct	385 ms	235268 KB	Output is correct
9	Correct	660 ms	235512 KB	Output is correct
10	Correct	784 ms	235488 KB	Output is correct
11	Correct	772 ms	235472 KB	Output is correct
12	Correct	436 ms	235312 KB	Output is correct
13	Correct	259 ms	235320 KB	Output is correct
14	Correct	380 ms	235256 KB	Output is correct
15	Correct	673 ms	235484 KB	Output is correct
16	Correct	309 ms	235572 KB	Output is correct
17	Correct	669 ms	235232 KB	Output is correct
18	Correct	632 ms	235640 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	648 ms	235484 KB	Output is correct
2	Correct	816 ms	235548 KB	Output is correct
3	Correct	801 ms	235544 KB	Output is correct
4	Correct	499 ms	235428 KB	Output is correct
5	Correct	381 ms	235728 KB	Output is correct
6	Correct	647 ms	235496 KB	Output is correct
7	Correct	708 ms	235732 KB	Output is correct
8	Correct	703 ms	235512 KB	Output is correct
9	Correct	631 ms	235512 KB	Output is correct
10	Correct	534 ms	235256 KB	Output is correct
11	Correct	467 ms	235264 KB	Output is correct
12	Correct	617 ms	235364 KB	Output is correct
13	Correct	762 ms	235592 KB	Output is correct
14	Correct	474 ms	235856 KB	Output is correct
15	Correct	681 ms	235380 KB	Output is correct
16	Correct	772 ms	235340 KB	Output is correct
17	Correct	663 ms	235512 KB	Output is correct
18	Correct	841 ms	235512 KB	Output is correct
19	Correct	278 ms	235316 KB	Output is correct
20	Correct	827 ms	235548 KB	Output is correct
21	Correct	494 ms	235728 KB	Output is correct
22	Correct	816 ms	235840 KB	Output is correct
23	Correct	366 ms	235544 KB	Output is correct
24	Correct	297 ms	235636 KB	Output is correct
25	Correct	530 ms	235568 KB	Output is correct
26	Correct	470 ms	235480 KB	Output is correct
27	Correct	885 ms	235768 KB	Output is correct
28	Correct	336 ms	235460 KB	Output is correct
29	Correct	775 ms	235800 KB	Output is correct
30	Correct	688 ms	235752 KB	Output is correct
31	Correct	352 ms	235448 KB	Output is correct
32	Correct	385 ms	235496 KB	Output is correct
33	Correct	266 ms	235512 KB	Output is correct
34	Correct	627 ms	235776 KB	Output is correct
35	Correct	329 ms	235652 KB	Output is correct
36	Correct	806 ms	235864 KB	Output is correct
37	Correct	371 ms	235852 KB	Output is correct
38	Correct	676 ms	235624 KB	Output is correct
39	Correct	330 ms	235640 KB	Output is correct
40	Correct	585 ms	235608 KB	Output is correct
41	Correct	510 ms	235820 KB	Output is correct
42	Correct	720 ms	235724 KB	Output is correct