답안 #483297

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483297	2021-10-28T14:34:10 Z	ntabc05101	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	76.3492 / 100	238 ms	79164 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);
	for (int i = 0; i < m; i++) {
		for (int j = prs[i]; j <= mxN; j += prs[i]) {
			b[j - 1] = min(b[j - 1], j - prs[i]);
		}
	}

	int mn = mxN + 1;
	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	61 ms	78492 KB	Output is correct
2	Correct	83 ms	78564 KB	Output is correct
3	Correct	58 ms	78520 KB	Output is correct
4	Correct	58 ms	78488 KB	Output is correct
5	Correct	70 ms	78488 KB	Output is correct
6	Correct	51 ms	78532 KB	Output is correct
7	Correct	59 ms	78564 KB	Output is correct
8	Correct	66 ms	78520 KB	Output is correct
9	Correct	87 ms	78532 KB	Output is correct
10	Correct	97 ms	78532 KB	Output is correct
11	Correct	96 ms	78488 KB	Output is correct
12	Correct	57 ms	78540 KB	Output is correct
13	Correct	161 ms	78444 KB	Output is correct
14	Correct	163 ms	78492 KB	Output is correct
15	Correct	82 ms	78480 KB	Output is correct
16	Correct	79 ms	78552 KB	Output is correct
17	Correct	75 ms	78528 KB	Output is correct
18	Correct	59 ms	78680 KB	Output is correct

Subtask #2

17.7777777778 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	68 ms	78532 KB	Output is correct
2	Correct	82 ms	78824 KB	Output is correct
3	Correct	210 ms	78784 KB	Output is correct
4	Correct	85 ms	78528 KB	Output is correct
5	Correct	151 ms	78884 KB	Output is correct
6	Correct	74 ms	78492 KB	Output is correct
7	Correct	70 ms	78528 KB	Output is correct
8	Correct	84 ms	78532 KB	Output is correct
9	Correct	166 ms	78808 KB	Output is correct
10	Correct	209 ms	78748 KB	Output is correct
11	Incorrect	199 ms	78632 KB	Output isn't correct
12	Correct	116 ms	78576 KB	Output is correct
13	Correct	65 ms	78496 KB	Output is correct
14	Correct	91 ms	78540 KB	Output is correct
15	Correct	165 ms	78640 KB	Output is correct
16	Correct	93 ms	78912 KB	Output is correct
17	Correct	175 ms	78492 KB	Output is correct
18	Incorrect	187 ms	78988 KB	Output isn't correct

Subtask #3

38.5714285714 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	178 ms	78796 KB	Output is correct
2	Correct	212 ms	78804 KB	Output is correct
3	Correct	217 ms	78924 KB	Output is correct
4	Incorrect	132 ms	78756 KB	Output isn't correct
5	Incorrect	99 ms	79092 KB	Output isn't correct
6	Correct	182 ms	78756 KB	Output is correct
7	Correct	151 ms	79000 KB	Output is correct
8	Correct	182 ms	78808 KB	Output is correct
9	Correct	173 ms	78796 KB	Output is correct
10	Correct	131 ms	78532 KB	Output is correct
11	Incorrect	118 ms	78628 KB	Output isn't correct
12	Correct	159 ms	78640 KB	Output is correct
13	Correct	215 ms	78852 KB	Output is correct
14	Correct	121 ms	79128 KB	Output is correct
15	Incorrect	166 ms	78660 KB	Output isn't correct
16	Correct	181 ms	78660 KB	Output is correct
17	Correct	184 ms	78780 KB	Output is correct
18	Correct	210 ms	78772 KB	Output is correct
19	Incorrect	76 ms	78660 KB	Output isn't correct
20	Correct	215 ms	78920 KB	Output is correct
21	Incorrect	139 ms	79124 KB	Output isn't correct
22	Correct	238 ms	79164 KB	Output is correct
23	Correct	109 ms	78980 KB	Output is correct
24	Correct	87 ms	78748 KB	Output is correct
25	Incorrect	156 ms	78848 KB	Output isn't correct
26	Incorrect	140 ms	78840 KB	Output isn't correct
27	Correct	233 ms	78988 KB	Output is correct
28	Incorrect	84 ms	78788 KB	Output isn't correct
29	Correct	211 ms	79112 KB	Output is correct
30	Correct	192 ms	79004 KB	Output is correct
31	Correct	100 ms	78888 KB	Output is correct
32	Incorrect	132 ms	78748 KB	Output isn't correct
33	Incorrect	79 ms	78788 KB	Output isn't correct
34	Correct	156 ms	78992 KB	Output is correct
35	Incorrect	93 ms	78792 KB	Output isn't correct
36	Correct	216 ms	79044 KB	Output is correct
37	Incorrect	100 ms	79072 KB	Output isn't correct
38	Correct	182 ms	78852 KB	Output is correct
39	Incorrect	96 ms	78948 KB	Output isn't correct
40	Correct	154 ms	78768 KB	Output is correct
41	Correct	138 ms	78944 KB	Output is correct
42	Incorrect	192 ms	78892 KB	Output isn't correct