답안 #483300

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483300	2021-10-28T14:47:09 Z	ntabc05101	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	230 ms	79224 KB

brunhilda

#include<bits/stdc++.h>
using namespace std;

const int mxN = 10000000;

int dp[mxN + 1], b[mxN + 1];

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int m, Q; cin >> m >> Q;
	int prs[m];
	for (int i = 0; i < m; i++) {
		cin >> prs[i];
	}
	iota(b + 1, b + mxN + 1, 1);
	sort(prs, prs + m);
	int mn = mxN + 1;
	for (int i = 0; i < m; i++) {
		int j;
		for (j = prs[i]; j <= mxN; j += prs[i]) {
			b[j - 1] = j - prs[i];
		}
		mn = min(mn, j - prs[i]);
	}

	for (int i = mxN; i; i--) {
		dp[i] = mxN + 1;
		mn = min(mn, b[i]);
		b[i] = mn;
	}
	for (int i = 1; i <= mxN; i++) {
		if (i == b[i]) {
			break;
		}
		dp[i] = dp[b[i]] + 1;
	}

	while (Q--) {
		int n; cin >> n;
		if (dp[n] == mxN + 1) {
			cout << "oo\n";
		}
		else {
			cout << dp[n] << "\n";
		}
	}

	return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	78532 KB	Output is correct
2	Correct	74 ms	78484 KB	Output is correct
3	Correct	57 ms	78480 KB	Output is correct
4	Correct	55 ms	78532 KB	Output is correct
5	Correct	67 ms	78480 KB	Output is correct
6	Correct	52 ms	78532 KB	Output is correct
7	Correct	55 ms	78468 KB	Output is correct
8	Correct	60 ms	78468 KB	Output is correct
9	Correct	79 ms	78516 KB	Output is correct
10	Correct	96 ms	78476 KB	Output is correct
11	Correct	84 ms	78484 KB	Output is correct
12	Correct	54 ms	78532 KB	Output is correct
13	Correct	143 ms	78472 KB	Output is correct
14	Correct	142 ms	78488 KB	Output is correct
15	Correct	75 ms	78564 KB	Output is correct
16	Correct	70 ms	78576 KB	Output is correct
17	Correct	69 ms	78556 KB	Output is correct
18	Correct	57 ms	78532 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	78528 KB	Output is correct
2	Correct	77 ms	78872 KB	Output is correct
3	Correct	172 ms	78772 KB	Output is correct
4	Correct	83 ms	78484 KB	Output is correct
5	Correct	123 ms	78676 KB	Output is correct
6	Correct	70 ms	78504 KB	Output is correct
7	Correct	64 ms	78608 KB	Output is correct
8	Correct	76 ms	78532 KB	Output is correct
9	Correct	142 ms	78788 KB	Output is correct
10	Correct	178 ms	78748 KB	Output is correct
11	Correct	172 ms	78660 KB	Output is correct
12	Correct	100 ms	78532 KB	Output is correct
13	Correct	61 ms	78496 KB	Output is correct
14	Correct	78 ms	78532 KB	Output is correct
15	Correct	141 ms	78640 KB	Output is correct
16	Correct	79 ms	78824 KB	Output is correct
17	Correct	146 ms	78480 KB	Output is correct
18	Correct	142 ms	78916 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	164 ms	78808 KB	Output is correct
2	Correct	181 ms	78820 KB	Output is correct
3	Correct	179 ms	78808 KB	Output is correct
4	Correct	125 ms	78728 KB	Output is correct
5	Correct	92 ms	79056 KB	Output is correct
6	Correct	167 ms	78756 KB	Output is correct
7	Correct	143 ms	78952 KB	Output is correct
8	Correct	152 ms	78796 KB	Output is correct
9	Correct	148 ms	78788 KB	Output is correct
10	Correct	121 ms	78636 KB	Output is correct
11	Correct	104 ms	78624 KB	Output is correct
12	Correct	137 ms	78576 KB	Output is correct
13	Correct	174 ms	78848 KB	Output is correct
14	Correct	114 ms	79116 KB	Output is correct
15	Correct	174 ms	78660 KB	Output is correct
16	Correct	165 ms	78572 KB	Output is correct
17	Correct	138 ms	78660 KB	Output is correct
18	Correct	185 ms	78788 KB	Output is correct
19	Correct	80 ms	78620 KB	Output is correct
20	Correct	213 ms	78892 KB	Output is correct
21	Correct	129 ms	79172 KB	Output is correct
22	Correct	205 ms	79224 KB	Output is correct
23	Correct	101 ms	78876 KB	Output is correct
24	Correct	84 ms	78732 KB	Output is correct
25	Correct	132 ms	78788 KB	Output is correct
26	Correct	128 ms	78868 KB	Output is correct
27	Correct	230 ms	79044 KB	Output is correct
28	Correct	85 ms	78788 KB	Output is correct
29	Correct	181 ms	79124 KB	Output is correct
30	Correct	169 ms	79004 KB	Output is correct
31	Correct	94 ms	78788 KB	Output is correct
32	Correct	104 ms	78740 KB	Output is correct
33	Correct	76 ms	78824 KB	Output is correct
34	Correct	141 ms	78992 KB	Output is correct
35	Correct	90 ms	78856 KB	Output is correct
36	Correct	188 ms	79044 KB	Output is correct
37	Correct	92 ms	79112 KB	Output is correct
38	Correct	176 ms	78764 KB	Output is correct
39	Correct	109 ms	78832 KB	Output is correct
40	Correct	138 ms	78740 KB	Output is correct
41	Correct	127 ms	78992 KB	Output is correct
42	Correct	194 ms	78880 KB	Output is correct