Submission #386034

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
386034	2021-04-05T13:14:39 Z	ronnith	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	293 ms	79980 KB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int MX = (int)1e7;
int n, q, sieve[MX + 1], dp[MX + 1];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> q;
	for(int i = 0;i < n;i ++) {
		int x; cin >> x;
		for(int j = x;j <= MX;j += x) {
			sieve[j] = x;
		}
		sieve[0] = x;
	}
	int ptr = 0;
	for(int i = 1;i <= MX;i ++) {
		while(ptr < i && (ptr + sieve[ptr] <= i || dp[ptr] == INT_MAX)) ptr ++;
		if(ptr == i) dp[i] = INT_MAX;
		else dp[i] = dp[ptr] + 1;
	}
	while(q --) {
		int x;
		cin >> x;
		if(dp[x] == INT_MAX) {
			cout << "oo\n";
		} else {
			cout << dp[x] << '\n';
		}
	}
	return 0;
}
// OUTPUT in new line.

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	113 ms	78572 KB	Output is correct
2	Correct	101 ms	78572 KB	Output is correct
3	Correct	87 ms	78572 KB	Output is correct
4	Correct	78 ms	78828 KB	Output is correct
5	Correct	104 ms	78572 KB	Output is correct
6	Correct	89 ms	78700 KB	Output is correct
7	Correct	88 ms	78700 KB	Output is correct
8	Correct	92 ms	78572 KB	Output is correct
9	Correct	122 ms	78572 KB	Output is correct
10	Correct	137 ms	78572 KB	Output is correct
11	Correct	122 ms	78572 KB	Output is correct
12	Correct	78 ms	78572 KB	Output is correct
13	Correct	210 ms	78572 KB	Output is correct
14	Correct	208 ms	78828 KB	Output is correct
15	Correct	110 ms	78572 KB	Output is correct
16	Correct	107 ms	78572 KB	Output is correct
17	Correct	104 ms	78956 KB	Output is correct
18	Correct	80 ms	78700 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	78700 KB	Output is correct
2	Correct	102 ms	79212 KB	Output is correct
3	Correct	258 ms	79084 KB	Output is correct
4	Correct	111 ms	78572 KB	Output is correct
5	Correct	182 ms	78956 KB	Output is correct
6	Correct	98 ms	78572 KB	Output is correct
7	Correct	93 ms	78724 KB	Output is correct
8	Correct	111 ms	78700 KB	Output is correct
9	Correct	214 ms	79108 KB	Output is correct
10	Correct	252 ms	79212 KB	Output is correct
11	Correct	245 ms	78828 KB	Output is correct
12	Correct	160 ms	78572 KB	Output is correct
13	Correct	85 ms	78572 KB	Output is correct
14	Correct	110 ms	78572 KB	Output is correct
15	Correct	207 ms	78828 KB	Output is correct
16	Correct	102 ms	79340 KB	Output is correct
17	Correct	219 ms	78700 KB	Output is correct
18	Correct	211 ms	79212 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	222 ms	79468 KB	Output is correct
2	Correct	270 ms	79212 KB	Output is correct
3	Correct	270 ms	79436 KB	Output is correct
4	Correct	176 ms	79468 KB	Output is correct
5	Correct	135 ms	79476 KB	Output is correct
6	Correct	228 ms	79496 KB	Output is correct
7	Correct	197 ms	79340 KB	Output is correct
8	Correct	225 ms	79340 KB	Output is correct
9	Correct	223 ms	79340 KB	Output is correct
10	Correct	171 ms	78828 KB	Output is correct
11	Correct	148 ms	78956 KB	Output is correct
12	Correct	193 ms	78828 KB	Output is correct
13	Correct	255 ms	79724 KB	Output is correct
14	Correct	181 ms	79852 KB	Output is correct
15	Correct	203 ms	78956 KB	Output is correct
16	Correct	230 ms	78828 KB	Output is correct
17	Correct	212 ms	79084 KB	Output is correct
18	Correct	264 ms	79340 KB	Output is correct
19	Correct	95 ms	78828 KB	Output is correct
20	Correct	266 ms	79596 KB	Output is correct
21	Correct	174 ms	79980 KB	Output is correct
22	Correct	288 ms	79596 KB	Output is correct
23	Correct	145 ms	79468 KB	Output is correct
24	Correct	116 ms	79596 KB	Output is correct
25	Correct	194 ms	79724 KB	Output is correct
26	Correct	173 ms	79468 KB	Output is correct
27	Correct	293 ms	79520 KB	Output is correct
28	Correct	112 ms	79596 KB	Output is correct
29	Correct	270 ms	79588 KB	Output is correct
30	Correct	269 ms	79468 KB	Output is correct
31	Correct	138 ms	79596 KB	Output is correct
32	Correct	143 ms	79596 KB	Output is correct
33	Correct	103 ms	79468 KB	Output is correct
34	Correct	224 ms	79340 KB	Output is correct
35	Correct	119 ms	79596 KB	Output is correct
36	Correct	284 ms	79596 KB	Output is correct
37	Correct	146 ms	79468 KB	Output is correct
38	Correct	238 ms	79588 KB	Output is correct
39	Correct	128 ms	79780 KB	Output is correct
40	Correct	201 ms	79468 KB	Output is correct
41	Correct	177 ms	79340 KB	Output is correct
42	Correct	243 ms	79724 KB	Output is correct