답안 #318120

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318120	2020-10-31T13:18:19 Z	shivensinha4	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	721 ms	158692 KB

brunhilda

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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;
}

Compilation message

brunhilda.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
brunhilda.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	201 ms	78820 KB	Output is correct
2	Correct	283 ms	156900 KB	Output is correct
3	Correct	227 ms	79788 KB	Output is correct
4	Correct	228 ms	156924 KB	Output is correct
5	Correct	262 ms	156900 KB	Output is correct
6	Correct	206 ms	78824 KB	Output is correct
7	Correct	225 ms	79844 KB	Output is correct
8	Correct	238 ms	82404 KB	Output is correct
9	Correct	297 ms	156884 KB	Output is correct
10	Correct	334 ms	156900 KB	Output is correct
11	Correct	327 ms	156892 KB	Output is correct
12	Correct	225 ms	156900 KB	Output is correct
13	Correct	542 ms	156896 KB	Output is correct
14	Correct	538 ms	157028 KB	Output is correct
15	Correct	295 ms	156904 KB	Output is correct
16	Correct	282 ms	156900 KB	Output is correct
17	Correct	280 ms	157028 KB	Output is correct
18	Correct	228 ms	157156 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	261 ms	157028 KB	Output is correct
2	Correct	287 ms	157668 KB	Output is correct
3	Correct	662 ms	157372 KB	Output is correct
4	Correct	303 ms	156900 KB	Output is correct
5	Correct	473 ms	157284 KB	Output is correct
6	Correct	286 ms	156900 KB	Output is correct
7	Correct	265 ms	157024 KB	Output is correct
8	Correct	310 ms	156900 KB	Output is correct
9	Correct	558 ms	157416 KB	Output is correct
10	Correct	658 ms	157412 KB	Output is correct
11	Correct	645 ms	157164 KB	Output is correct
12	Correct	383 ms	156900 KB	Output is correct
13	Correct	243 ms	156900 KB	Output is correct
14	Correct	311 ms	156896 KB	Output is correct
15	Correct	543 ms	157284 KB	Output is correct
16	Correct	287 ms	157668 KB	Output is correct
17	Correct	551 ms	157028 KB	Output is correct
18	Correct	555 ms	157668 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	555 ms	157668 KB	Output is correct
2	Correct	677 ms	157668 KB	Output is correct
3	Correct	672 ms	157924 KB	Output is correct
4	Correct	419 ms	157864 KB	Output is correct
5	Correct	330 ms	158656 KB	Output is correct
6	Correct	564 ms	157888 KB	Output is correct
7	Correct	488 ms	158180 KB	Output is correct
8	Correct	562 ms	157664 KB	Output is correct
9	Correct	558 ms	157568 KB	Output is correct
10	Correct	447 ms	157032 KB	Output is correct
11	Correct	396 ms	157180 KB	Output is correct
12	Correct	508 ms	157156 KB	Output is correct
13	Correct	637 ms	158168 KB	Output is correct
14	Correct	373 ms	158308 KB	Output is correct
15	Correct	525 ms	157284 KB	Output is correct
16	Correct	591 ms	157196 KB	Output is correct
17	Correct	524 ms	157428 KB	Output is correct
18	Correct	672 ms	157540 KB	Output is correct
19	Correct	257 ms	157156 KB	Output is correct
20	Correct	664 ms	157796 KB	Output is correct
21	Correct	441 ms	158360 KB	Output is correct
22	Correct	690 ms	158564 KB	Output is correct
23	Correct	340 ms	158120 KB	Output is correct
24	Correct	282 ms	157924 KB	Output is correct
25	Correct	452 ms	157924 KB	Output is correct
26	Correct	409 ms	157796 KB	Output is correct
27	Correct	721 ms	158180 KB	Output is correct
28	Correct	283 ms	158052 KB	Output is correct
29	Correct	645 ms	158564 KB	Output is correct
30	Correct	599 ms	158436 KB	Output is correct
31	Correct	319 ms	157928 KB	Output is correct
32	Correct	370 ms	157924 KB	Output is correct
33	Correct	280 ms	157796 KB	Output is correct
34	Correct	505 ms	158176 KB	Output is correct
35	Correct	307 ms	158052 KB	Output is correct
36	Correct	661 ms	158560 KB	Output is correct
37	Correct	346 ms	158692 KB	Output is correct
38	Correct	547 ms	158052 KB	Output is correct
39	Correct	299 ms	158052 KB	Output is correct
40	Correct	471 ms	158052 KB	Output is correct
41	Correct	441 ms	158148 KB	Output is correct
42	Correct	613 ms	158052 KB	Output is correct