Submission #318122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
318122	2020-10-31T13:18:58 Z	shivensinha4	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	660 ms	157540 KB

brunhilda

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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	153 ms	78864 KB	Output is correct
2	Correct	229 ms	156900 KB	Output is correct
3	Correct	171 ms	79844 KB	Output is correct
4	Correct	174 ms	157028 KB	Output is correct
5	Correct	199 ms	156900 KB	Output is correct
6	Correct	149 ms	78820 KB	Output is correct
7	Correct	169 ms	79848 KB	Output is correct
8	Correct	177 ms	82404 KB	Output is correct
9	Correct	240 ms	156888 KB	Output is correct
10	Correct	278 ms	156900 KB	Output is correct
11	Correct	261 ms	156900 KB	Output is correct
12	Correct	171 ms	156900 KB	Output is correct
13	Correct	466 ms	156900 KB	Output is correct
14	Correct	467 ms	156884 KB	Output is correct
15	Correct	238 ms	156920 KB	Output is correct
16	Correct	221 ms	156900 KB	Output is correct
17	Correct	220 ms	156880 KB	Output is correct
18	Correct	183 ms	156900 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	206 ms	156900 KB	Output is correct
2	Correct	230 ms	156900 KB	Output is correct
3	Correct	585 ms	156880 KB	Output is correct
4	Correct	261 ms	156888 KB	Output is correct
5	Correct	413 ms	156848 KB	Output is correct
6	Correct	215 ms	156900 KB	Output is correct
7	Correct	207 ms	157028 KB	Output is correct
8	Correct	246 ms	156900 KB	Output is correct
9	Correct	476 ms	157024 KB	Output is correct
10	Correct	582 ms	156904 KB	Output is correct
11	Correct	569 ms	156900 KB	Output is correct
12	Correct	322 ms	156900 KB	Output is correct
13	Correct	186 ms	156992 KB	Output is correct
14	Correct	254 ms	156900 KB	Output is correct
15	Correct	472 ms	156900 KB	Output is correct
16	Correct	232 ms	156900 KB	Output is correct
17	Correct	487 ms	156900 KB	Output is correct
18	Correct	470 ms	156900 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	478 ms	157028 KB	Output is correct
2	Correct	596 ms	156900 KB	Output is correct
3	Correct	594 ms	157028 KB	Output is correct
4	Correct	351 ms	157156 KB	Output is correct
5	Correct	269 ms	157252 KB	Output is correct
6	Correct	477 ms	157284 KB	Output is correct
7	Correct	434 ms	157028 KB	Output is correct
8	Correct	485 ms	157156 KB	Output is correct
9	Correct	478 ms	157028 KB	Output is correct
10	Correct	389 ms	156884 KB	Output is correct
11	Correct	329 ms	156900 KB	Output is correct
12	Correct	444 ms	157012 KB	Output is correct
13	Correct	563 ms	157148 KB	Output is correct
14	Correct	319 ms	157540 KB	Output is correct
15	Correct	466 ms	157028 KB	Output is correct
16	Correct	515 ms	157156 KB	Output is correct
17	Correct	473 ms	156888 KB	Output is correct
18	Correct	593 ms	157028 KB	Output is correct
19	Correct	205 ms	156900 KB	Output is correct
20	Correct	592 ms	157028 KB	Output is correct
21	Correct	369 ms	157536 KB	Output is correct
22	Correct	600 ms	157160 KB	Output is correct
23	Correct	275 ms	157156 KB	Output is correct
24	Correct	225 ms	157284 KB	Output is correct
25	Correct	398 ms	157284 KB	Output is correct
26	Correct	354 ms	157156 KB	Output is correct
27	Correct	660 ms	157028 KB	Output is correct
28	Correct	233 ms	157284 KB	Output is correct
29	Correct	576 ms	157284 KB	Output is correct
30	Correct	532 ms	157284 KB	Output is correct
31	Correct	276 ms	157156 KB	Output is correct
32	Correct	298 ms	157284 KB	Output is correct
33	Correct	197 ms	157156 KB	Output is correct
34	Correct	433 ms	157008 KB	Output is correct
35	Correct	240 ms	157156 KB	Output is correct
36	Correct	581 ms	157156 KB	Output is correct
37	Correct	270 ms	157160 KB	Output is correct
38	Correct	479 ms	157156 KB	Output is correct
39	Correct	243 ms	157156 KB	Output is correct
40	Correct	418 ms	157140 KB	Output is correct
41	Correct	372 ms	157028 KB	Output is correct
42	Correct	526 ms	157272 KB	Output is correct