답안 #734615

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734615	2023-05-02T17:17:29 Z	DAleksa	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	97.7778 / 100	519 ms	194580 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;
        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	156 ms	163556 KB	Output isn't correct
2	Correct	225 ms	185404 KB	Output is correct
3	Correct	216 ms	181388 KB	Output is correct
4	Correct	134 ms	159884 KB	Output is correct
5	Correct	218 ms	167300 KB	Output is correct
6	Incorrect	172 ms	163616 KB	Output isn't correct
7	Correct	221 ms	181472 KB	Output is correct
8	Correct	250 ms	186320 KB	Output is correct
9	Correct	275 ms	189080 KB	Output is correct
10	Correct	328 ms	190048 KB	Output is correct
11	Correct	372 ms	184360 KB	Output is correct
12	Correct	131 ms	159024 KB	Output is correct
13	Correct	460 ms	193360 KB	Output is correct
14	Correct	441 ms	193376 KB	Output is correct
15	Correct	270 ms	184496 KB	Output is correct
16	Correct	268 ms	185344 KB	Output is correct
17	Correct	245 ms	167160 KB	Output is correct
18	Correct	166 ms	159888 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	183 ms	163616 KB	Output is correct
2	Correct	197 ms	166040 KB	Output is correct
3	Correct	466 ms	193932 KB	Output is correct
4	Correct	270 ms	172792 KB	Output is correct
5	Correct	374 ms	188460 KB	Output is correct
6	Correct	231 ms	180376 KB	Output is correct
7	Correct	176 ms	163588 KB	Output is correct
8	Correct	263 ms	171092 KB	Output is correct
9	Correct	412 ms	190600 KB	Output is correct
10	Correct	477 ms	194052 KB	Output is correct
11	Correct	435 ms	193676 KB	Output is correct
12	Correct	360 ms	186796 KB	Output is correct
13	Correct	162 ms	166484 KB	Output is correct
14	Correct	235 ms	172812 KB	Output is correct
15	Correct	403 ms	192748 KB	Output is correct
16	Correct	196 ms	166084 KB	Output is correct
17	Correct	420 ms	192924 KB	Output is correct
18	Correct	401 ms	191364 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	379 ms	193308 KB	Output is correct
2	Correct	429 ms	193860 KB	Output is correct
3	Correct	482 ms	194200 KB	Output is correct
4	Correct	320 ms	188352 KB	Output is correct
5	Correct	206 ms	166844 KB	Output is correct
6	Correct	408 ms	191776 KB	Output is correct
7	Correct	334 ms	185336 KB	Output is correct
8	Correct	381 ms	193352 KB	Output is correct
9	Correct	392 ms	193292 KB	Output is correct
10	Correct	344 ms	184228 KB	Output is correct
11	Correct	297 ms	180164 KB	Output is correct
12	Correct	386 ms	191448 KB	Output is correct
13	Correct	410 ms	193000 KB	Output is correct
14	Correct	338 ms	191324 KB	Output is correct
15	Correct	409 ms	193060 KB	Output is correct
16	Correct	417 ms	193324 KB	Output is correct
17	Correct	369 ms	189184 KB	Output is correct
18	Correct	438 ms	193968 KB	Output is correct
19	Correct	171 ms	173472 KB	Output is correct
20	Correct	477 ms	193980 KB	Output is correct
21	Correct	355 ms	192752 KB	Output is correct
22	Correct	519 ms	194396 KB	Output is correct
23	Correct	238 ms	168096 KB	Output is correct
24	Correct	186 ms	164460 KB	Output is correct
25	Correct	363 ms	187052 KB	Output is correct
26	Correct	345 ms	188408 KB	Output is correct
27	Correct	475 ms	194580 KB	Output is correct
28	Correct	227 ms	171136 KB	Output is correct
29	Correct	472 ms	191224 KB	Output is correct
30	Correct	423 ms	189764 KB	Output is correct
31	Correct	267 ms	172100 KB	Output is correct
32	Correct	282 ms	175912 KB	Output is correct
33	Correct	154 ms	161380 KB	Output is correct
34	Correct	373 ms	185268 KB	Output is correct
35	Correct	216 ms	171800 KB	Output is correct
36	Correct	450 ms	194144 KB	Output is correct
37	Correct	212 ms	166812 KB	Output is correct
38	Correct	428 ms	191744 KB	Output is correct
39	Correct	202 ms	166388 KB	Output is correct
40	Correct	406 ms	190144 KB	Output is correct
41	Correct	363 ms	188428 KB	Output is correct
42	Correct	446 ms	193972 KB	Output is correct