답안 #734613

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

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 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;
        assert(x != 0);
        if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	156 ms	163508 KB	Output isn't correct
2	Correct	217 ms	185392 KB	Output is correct
3	Correct	196 ms	181592 KB	Output is correct
4	Correct	122 ms	159844 KB	Output is correct
5	Correct	193 ms	167240 KB	Output is correct
6	Incorrect	144 ms	163604 KB	Output isn't correct
7	Correct	204 ms	181380 KB	Output is correct
8	Correct	213 ms	186400 KB	Output is correct
9	Correct	258 ms	189056 KB	Output is correct
10	Correct	305 ms	190096 KB	Output is correct
11	Correct	260 ms	184392 KB	Output is correct
12	Correct	113 ms	159068 KB	Output is correct
13	Correct	381 ms	193396 KB	Output is correct
14	Correct	405 ms	193344 KB	Output is correct
15	Correct	236 ms	184560 KB	Output is correct
16	Correct	213 ms	185384 KB	Output is correct
17	Correct	195 ms	167180 KB	Output is correct
18	Correct	116 ms	159844 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	168 ms	163584 KB	Output is correct
2	Correct	201 ms	166136 KB	Output is correct
3	Correct	463 ms	194000 KB	Output is correct
4	Correct	232 ms	172860 KB	Output is correct
5	Correct	342 ms	188596 KB	Output is correct
6	Correct	235 ms	180372 KB	Output is correct
7	Correct	151 ms	163656 KB	Output is correct
8	Correct	220 ms	171072 KB	Output is correct
9	Correct	382 ms	190572 KB	Output is correct
10	Correct	538 ms	194024 KB	Output is correct
11	Correct	413 ms	193668 KB	Output is correct
12	Correct	335 ms	186744 KB	Output is correct
13	Correct	194 ms	166548 KB	Output is correct
14	Correct	238 ms	172800 KB	Output is correct
15	Correct	456 ms	192676 KB	Output is correct
16	Correct	206 ms	166076 KB	Output is correct
17	Correct	474 ms	192876 KB	Output is correct
18	Correct	427 ms	191344 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	437 ms	193360 KB	Output is correct
2	Correct	486 ms	193856 KB	Output is correct
3	Correct	453 ms	194004 KB	Output is correct
4	Correct	360 ms	188404 KB	Output is correct
5	Correct	216 ms	166892 KB	Output is correct
6	Correct	446 ms	191728 KB	Output is correct
7	Correct	386 ms	185244 KB	Output is correct
8	Correct	421 ms	193336 KB	Output is correct
9	Correct	473 ms	193320 KB	Output is correct
10	Correct	377 ms	184252 KB	Output is correct
11	Correct	358 ms	180184 KB	Output is correct
12	Correct	500 ms	191480 KB	Output is correct
13	Correct	629 ms	192840 KB	Output is correct
14	Correct	412 ms	191260 KB	Output is correct
15	Correct	463 ms	193092 KB	Output is correct
16	Correct	425 ms	193392 KB	Output is correct
17	Correct	390 ms	189268 KB	Output is correct
18	Correct	467 ms	193848 KB	Output is correct
19	Correct	195 ms	173380 KB	Output is correct
20	Correct	476 ms	193968 KB	Output is correct
21	Correct	378 ms	192792 KB	Output is correct
22	Correct	577 ms	194376 KB	Output is correct
23	Correct	255 ms	168096 KB	Output is correct
24	Correct	210 ms	164316 KB	Output is correct
25	Correct	398 ms	187000 KB	Output is correct
26	Correct	366 ms	188348 KB	Output is correct
27	Correct	508 ms	194360 KB	Output is correct
28	Correct	214 ms	171032 KB	Output is correct
29	Correct	488 ms	191220 KB	Output is correct
30	Correct	457 ms	189448 KB	Output is correct
31	Correct	267 ms	172100 KB	Output is correct
32	Correct	305 ms	175856 KB	Output is correct
33	Correct	162 ms	161396 KB	Output is correct
34	Correct	375 ms	185256 KB	Output is correct
35	Correct	231 ms	171692 KB	Output is correct
36	Correct	522 ms	194208 KB	Output is correct
37	Correct	229 ms	166760 KB	Output is correct
38	Correct	468 ms	191736 KB	Output is correct
39	Correct	211 ms	166436 KB	Output is correct
40	Correct	428 ms	190100 KB	Output is correct
41	Correct	348 ms	188440 KB	Output is correct
42	Correct	450 ms	193820 KB	Output is correct