oj.uz

Submission #483300

# Submission time Handle Problem Language Result Execution time Memory
483300 2021-10-28T14:47:09 Z ntabc05101 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 230 ms 79224 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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