답안 #734620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734620	2023-05-02T17:20:28 Z	DAleksa	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	97.7778 / 100	552 ms	194424 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	145 ms	163708 KB	Output isn't correct
2	Correct	207 ms	185376 KB	Output is correct
3	Correct	195 ms	181368 KB	Output is correct
4	Correct	117 ms	159820 KB	Output is correct
5	Correct	184 ms	167260 KB	Output is correct
6	Incorrect	142 ms	163504 KB	Output isn't correct
7	Correct	197 ms	181380 KB	Output is correct
8	Correct	208 ms	186444 KB	Output is correct
9	Correct	254 ms	189044 KB	Output is correct
10	Correct	296 ms	190044 KB	Output is correct
11	Correct	268 ms	184308 KB	Output is correct
12	Correct	112 ms	158976 KB	Output is correct
13	Correct	388 ms	193324 KB	Output is correct
14	Correct	377 ms	193468 KB	Output is correct
15	Correct	238 ms	184564 KB	Output is correct
16	Correct	214 ms	185460 KB	Output is correct
17	Correct	183 ms	167212 KB	Output is correct
18	Correct	120 ms	159824 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	163588 KB	Output is correct
2	Correct	178 ms	166072 KB	Output is correct
3	Correct	415 ms	193984 KB	Output is correct
4	Correct	227 ms	172776 KB	Output is correct
5	Correct	336 ms	188500 KB	Output is correct
6	Correct	197 ms	180368 KB	Output is correct
7	Correct	154 ms	163640 KB	Output is correct
8	Correct	224 ms	171032 KB	Output is correct
9	Correct	374 ms	190716 KB	Output is correct
10	Correct	425 ms	193972 KB	Output is correct
11	Correct	456 ms	193708 KB	Output is correct
12	Correct	308 ms	186740 KB	Output is correct
13	Correct	157 ms	166652 KB	Output is correct
14	Correct	229 ms	172848 KB	Output is correct
15	Correct	492 ms	192764 KB	Output is correct
16	Correct	171 ms	166068 KB	Output is correct
17	Correct	404 ms	192900 KB	Output is correct
18	Correct	421 ms	191348 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	458 ms	193384 KB	Output is correct
2	Correct	552 ms	193900 KB	Output is correct
3	Correct	541 ms	194028 KB	Output is correct
4	Correct	363 ms	188292 KB	Output is correct
5	Correct	231 ms	166804 KB	Output is correct
6	Correct	436 ms	191740 KB	Output is correct
7	Correct	380 ms	185224 KB	Output is correct
8	Correct	446 ms	193320 KB	Output is correct
9	Correct	458 ms	193332 KB	Output is correct
10	Correct	346 ms	184248 KB	Output is correct
11	Correct	331 ms	180228 KB	Output is correct
12	Correct	406 ms	191508 KB	Output is correct
13	Correct	455 ms	192844 KB	Output is correct
14	Correct	368 ms	191352 KB	Output is correct
15	Correct	454 ms	193052 KB	Output is correct
16	Correct	452 ms	193360 KB	Output is correct
17	Correct	397 ms	189252 KB	Output is correct
18	Correct	523 ms	193920 KB	Output is correct
19	Correct	183 ms	173464 KB	Output is correct
20	Correct	487 ms	194040 KB	Output is correct
21	Correct	366 ms	192720 KB	Output is correct
22	Correct	525 ms	194368 KB	Output is correct
23	Correct	247 ms	168108 KB	Output is correct
24	Correct	184 ms	164420 KB	Output is correct
25	Correct	370 ms	187040 KB	Output is correct
26	Correct	358 ms	188332 KB	Output is correct
27	Correct	488 ms	194424 KB	Output is correct
28	Correct	214 ms	171044 KB	Output is correct
29	Correct	467 ms	191224 KB	Output is correct
30	Correct	470 ms	189476 KB	Output is correct
31	Correct	254 ms	172088 KB	Output is correct
32	Correct	315 ms	175908 KB	Output is correct
33	Correct	161 ms	161348 KB	Output is correct
34	Correct	390 ms	185304 KB	Output is correct
35	Correct	222 ms	171812 KB	Output is correct
36	Correct	480 ms	194208 KB	Output is correct
37	Correct	225 ms	166940 KB	Output is correct
38	Correct	451 ms	191744 KB	Output is correct
39	Correct	230 ms	166364 KB	Output is correct
40	Correct	424 ms	190072 KB	Output is correct
41	Correct	340 ms	188408 KB	Output is correct
42	Correct	485 ms	193896 KB	Output is correct