답안 #734621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734621	2023-05-02T17:20:42 Z	DAleksa	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	97.7778 / 100	616 ms	213784 KB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int N = 11000000 + 10;
int n, q;
vector<int> p;
vector<int> v;
int cnt[N];
int prime[N];
int prv[N];
int dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    p.resize(n);
    for(int i = 0; i < n; i++) cin >> p[i];
    for(int i = p.size() - 1; i >= 0; i--) {
        for(int j = p[i]; j < N; j += p[i]) {
            if(prime[j] == 0) {
                cnt[j]++;
                prime[j] = p[i];
            }
        }
    }
    cnt[0]++;
    prime[0] = p.back();
    for(int i = 0; i < N; i++) for(int j = 0; j < cnt[i]; j++) v.push_back(i);
    int j = 0;
    for(int i = 1; i < N; i++) {
        while(v[j] + prime[v[j]] <= i) j++;
        prv[i] = v[j];
    }
    for(int i = 1; i < N; i++) {
        if(prv[i] == i) dp[i] = -1;
        else dp[i] = dp[prv[i]] + 1;
    }
    while(q--) {
        int x;
        cin >> x;
        if(x < p.back()) cout << "1\n";
        else if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	169 ms	179904 KB	Output isn't correct
2	Correct	291 ms	203900 KB	Output is correct
3	Correct	243 ms	199496 KB	Output is correct
4	Correct	173 ms	175836 KB	Output is correct
5	Correct	214 ms	183928 KB	Output is correct
6	Incorrect	172 ms	179936 KB	Output isn't correct
7	Correct	236 ms	199504 KB	Output is correct
8	Correct	246 ms	205128 KB	Output is correct
9	Correct	320 ms	207884 KB	Output is correct
10	Correct	348 ms	209104 KB	Output is correct
11	Correct	316 ms	202892 KB	Output is correct
12	Correct	169 ms	174952 KB	Output is correct
13	Correct	463 ms	212596 KB	Output is correct
14	Correct	444 ms	212616 KB	Output is correct
15	Correct	286 ms	202936 KB	Output is correct
16	Correct	257 ms	203900 KB	Output is correct
17	Correct	225 ms	183876 KB	Output is correct
18	Correct	138 ms	175784 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	188 ms	179996 KB	Output is correct
2	Correct	206 ms	182656 KB	Output is correct
3	Correct	530 ms	213276 KB	Output is correct
4	Correct	294 ms	190012 KB	Output is correct
5	Correct	427 ms	207312 KB	Output is correct
6	Correct	223 ms	198392 KB	Output is correct
7	Correct	168 ms	179928 KB	Output is correct
8	Correct	274 ms	188180 KB	Output is correct
9	Correct	434 ms	209572 KB	Output is correct
10	Correct	521 ms	213332 KB	Output is correct
11	Correct	499 ms	212988 KB	Output is correct
12	Correct	366 ms	205428 KB	Output is correct
13	Correct	177 ms	183172 KB	Output is correct
14	Correct	269 ms	190088 KB	Output is correct
15	Correct	453 ms	211876 KB	Output is correct
16	Correct	341 ms	182552 KB	Output is correct
17	Correct	463 ms	212172 KB	Output is correct
18	Correct	456 ms	210392 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	454 ms	212612 KB	Output is correct
2	Correct	581 ms	213148 KB	Output is correct
3	Correct	616 ms	213312 KB	Output is correct
4	Correct	413 ms	207196 KB	Output is correct
5	Correct	243 ms	183440 KB	Output is correct
6	Correct	481 ms	210912 KB	Output is correct
7	Correct	445 ms	203632 KB	Output is correct
8	Correct	545 ms	212580 KB	Output is correct
9	Correct	451 ms	212644 KB	Output is correct
10	Correct	408 ms	202544 KB	Output is correct
11	Correct	350 ms	198132 KB	Output is correct
12	Correct	433 ms	210560 KB	Output is correct
13	Correct	496 ms	212192 KB	Output is correct
14	Correct	356 ms	210348 KB	Output is correct
15	Correct	419 ms	212436 KB	Output is correct
16	Correct	441 ms	212776 KB	Output is correct
17	Correct	411 ms	207984 KB	Output is correct
18	Correct	458 ms	213232 KB	Output is correct
19	Correct	187 ms	190652 KB	Output is correct
20	Correct	468 ms	213440 KB	Output is correct
21	Correct	363 ms	211884 KB	Output is correct
22	Correct	463 ms	213784 KB	Output is correct
23	Correct	229 ms	184800 KB	Output is correct
24	Correct	185 ms	180720 KB	Output is correct
25	Correct	360 ms	205552 KB	Output is correct
26	Correct	360 ms	207108 KB	Output is correct
27	Correct	494 ms	213768 KB	Output is correct
28	Correct	215 ms	188056 KB	Output is correct
29	Correct	451 ms	210028 KB	Output is correct
30	Correct	434 ms	208196 KB	Output is correct
31	Correct	253 ms	189164 KB	Output is correct
32	Correct	297 ms	193328 KB	Output is correct
33	Correct	160 ms	177488 KB	Output is correct
34	Correct	368 ms	203604 KB	Output is correct
35	Correct	226 ms	188868 KB	Output is correct
36	Correct	468 ms	213560 KB	Output is correct
37	Correct	223 ms	183420 KB	Output is correct
38	Correct	451 ms	210956 KB	Output is correct
39	Correct	211 ms	182964 KB	Output is correct
40	Correct	394 ms	209176 KB	Output is correct
41	Correct	371 ms	207232 KB	Output is correct
42	Correct	442 ms	213204 KB	Output is correct