답안 #152531

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152531 2019-09-08T09:21:55 Z dolphingarlic Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
887 ms 235884 KB
#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")
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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