Submission #318118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
318118	2020-10-31T13:17:17 Z	shivensinha4	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	685 ms	158704 KB

brunhilda

#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 2e7;
int jmp[MXN+2], ans[MXN+2];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int m, q; cin >> m >> q;
	for_(i, 0, m) {
		int k; cin >> k;
		for (int j = k; j <= MXN; j += k) {
			jmp[j-1] = max(jmp[j-1], k-1);
		}
	}
	
	for (int i = MXN; i >= 1; i--) jmp[i] = max(jmp[i], jmp[i+1]-1);
	
	for_(i, 1, MXN+1) if (jmp[i] and (ans[i-jmp[i]] or i == jmp[i])) ans[i] = ans[i-jmp[i]]+1;
	
	for_(i, 0, q) {
		int k; cin >> k;
		if (ans[k]) cout << ans[k];
		else cout << "oo";
		cout << endl;
	}

	return 0;
}

Subtask #1

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	190 ms	78828 KB	Output is correct
2	Correct	259 ms	156948 KB	Output is correct
3	Correct	219 ms	79828 KB	Output is correct
4	Correct	233 ms	157108 KB	Output is correct
5	Correct	248 ms	156908 KB	Output is correct
6	Correct	196 ms	78828 KB	Output is correct
7	Correct	246 ms	79852 KB	Output is correct
8	Correct	236 ms	82284 KB	Output is correct
9	Correct	281 ms	156908 KB	Output is correct
10	Correct	323 ms	157036 KB	Output is correct
11	Correct	304 ms	157100 KB	Output is correct
12	Correct	214 ms	157036 KB	Output is correct
13	Correct	506 ms	156912 KB	Output is correct
14	Correct	523 ms	157032 KB	Output is correct
15	Correct	278 ms	156908 KB	Output is correct
16	Correct	265 ms	156908 KB	Output is correct
17	Correct	270 ms	157036 KB	Output is correct
18	Correct	237 ms	157036 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	262 ms	157068 KB	Output is correct
2	Correct	329 ms	157676 KB	Output is correct
3	Correct	638 ms	157416 KB	Output is correct
4	Correct	295 ms	156968 KB	Output is correct
5	Correct	446 ms	157292 KB	Output is correct
6	Correct	286 ms	156908 KB	Output is correct
7	Correct	251 ms	157036 KB	Output is correct
8	Correct	294 ms	156908 KB	Output is correct
9	Correct	517 ms	157420 KB	Output is correct
10	Correct	646 ms	157496 KB	Output is correct
11	Correct	611 ms	157164 KB	Output is correct
12	Correct	364 ms	156856 KB	Output is correct
13	Correct	232 ms	156908 KB	Output is correct
14	Correct	293 ms	156908 KB	Output is correct
15	Correct	525 ms	157160 KB	Output is correct
16	Correct	280 ms	157556 KB	Output is correct
17	Correct	544 ms	156908 KB	Output is correct
18	Correct	518 ms	157676 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	554 ms	157676 KB	Output is correct
2	Correct	653 ms	157544 KB	Output is correct
3	Correct	635 ms	157800 KB	Output is correct
4	Correct	390 ms	157804 KB	Output is correct
5	Correct	322 ms	158700 KB	Output is correct
6	Correct	524 ms	157932 KB	Output is correct
7	Correct	467 ms	158184 KB	Output is correct
8	Correct	529 ms	157616 KB	Output is correct
9	Correct	537 ms	157672 KB	Output is correct
10	Correct	476 ms	157128 KB	Output is correct
11	Correct	376 ms	157164 KB	Output is correct
12	Correct	500 ms	157160 KB	Output is correct
13	Correct	631 ms	158056 KB	Output is correct
14	Correct	388 ms	158188 KB	Output is correct
15	Correct	506 ms	157164 KB	Output is correct
16	Correct	585 ms	157292 KB	Output is correct
17	Correct	533 ms	157292 KB	Output is correct
18	Correct	649 ms	157580 KB	Output is correct
19	Correct	247 ms	157296 KB	Output is correct
20	Correct	663 ms	157804 KB	Output is correct
21	Correct	424 ms	158388 KB	Output is correct
22	Correct	657 ms	158704 KB	Output is correct
23	Correct	324 ms	158164 KB	Output is correct
24	Correct	265 ms	157932 KB	Output is correct
25	Correct	446 ms	157932 KB	Output is correct
26	Correct	401 ms	157804 KB	Output is correct
27	Correct	685 ms	158188 KB	Output is correct
28	Correct	276 ms	158056 KB	Output is correct
29	Correct	634 ms	158596 KB	Output is correct
30	Correct	591 ms	158540 KB	Output is correct
31	Correct	302 ms	157932 KB	Output is correct
32	Correct	346 ms	158112 KB	Output is correct
33	Correct	253 ms	157952 KB	Output is correct
34	Correct	495 ms	158188 KB	Output is correct
35	Correct	282 ms	158056 KB	Output is correct
36	Correct	657 ms	158464 KB	Output is correct
37	Correct	312 ms	158700 KB	Output is correct
38	Correct	528 ms	157932 KB	Output is correct
39	Correct	283 ms	157932 KB	Output is correct
40	Correct	462 ms	157932 KB	Output is correct
41	Correct	441 ms	158464 KB	Output is correct
42	Correct	610 ms	158220 KB	Output is correct