oj.uz

답안 #483295

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483295 2021-10-28T14:32:29 Z ntabc05101 Brunhilda’s Birthday (BOI13_brunhilda) C++14
76.3492 / 100
 221 ms 79684 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);
	for (int i = 0; i < m; i++) {
		for (int j = prs[i]; j <= mxN; j += prs[i]) {
			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 49 ms 78544 KB Output is correct
2 Correct 70 ms 78596 KB Output is correct
3 Correct 56 ms 78476 KB Output is correct
4 Correct 54 ms 78660 KB Output is correct
5 Correct 64 ms 78532 KB Output is correct
6 Correct 51 ms 78460 KB Output is correct
7 Correct 55 ms 78576 KB Output is correct
8 Correct 60 ms 78544 KB Output is correct
9 Correct 79 ms 78472 KB Output is correct
10 Correct 90 ms 78532 KB Output is correct
11 Correct 85 ms 78484 KB Output is correct
12 Correct 57 ms 78532 KB Output is correct
13 Correct 144 ms 78488 KB Output is correct
14 Correct 142 ms 78528 KB Output is correct
15 Correct 76 ms 78492 KB Output is correct
16 Correct 72 ms 78532 KB Output is correct
17 Correct 78 ms 78536 KB Output is correct
18 Correct 56 ms 78532 KB Output is correct

Subtask #2
17.7777777778 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 78704 KB Output is correct
2 Correct 79 ms 79220 KB Output is correct
3 Correct 188 ms 79072 KB Output is correct
4 Correct 76 ms 78504 KB Output is correct
5 Correct 130 ms 79040 KB Output is correct
6 Correct 72 ms 78492 KB Output is correct
7 Correct 63 ms 78660 KB Output is correct
8 Correct 76 ms 78488 KB Output is correct
9 Correct 141 ms 79244 KB Output is correct
10 Correct 171 ms 79220 KB Output is correct
11 Incorrect 170 ms 78900 KB Output isn't correct
12 Correct 96 ms 78480 KB Output is correct
13 Correct 60 ms 78520 KB Output is correct
14 Correct 77 ms 78584 KB Output is correct
15 Correct 156 ms 78912 KB Output is correct
16 Correct 75 ms 79428 KB Output is correct
17 Correct 147 ms 78516 KB Output is correct
18 Incorrect 162 ms 79372 KB Output isn't correct

Subtask #3
38.5714285714 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 149 ms 79300 KB Output is correct
2 Correct 177 ms 79280 KB Output is correct
3 Correct 178 ms 79344 KB Output is correct
4 Incorrect 130 ms 79256 KB Output isn't correct
5 Incorrect 91 ms 79576 KB Output isn't correct
6 Correct 157 ms 79380 KB Output is correct
7 Correct 133 ms 79556 KB Output is correct
8 Correct 166 ms 79336 KB Output is correct
9 Correct 155 ms 79264 KB Output is correct
10 Correct 115 ms 78704 KB Output is correct
11 Incorrect 103 ms 78740 KB Output isn't correct
12 Correct 135 ms 78792 KB Output is correct
13 Correct 197 ms 79388 KB Output is correct
14 Correct 113 ms 79560 KB Output is correct
15 Incorrect 144 ms 78876 KB Output isn't correct
16 Correct 183 ms 78836 KB Output is correct
17 Correct 141 ms 79168 KB Output is correct
18 Correct 180 ms 79296 KB Output is correct
19 Incorrect 67 ms 78768 KB Output isn't correct
20 Correct 221 ms 79376 KB Output is correct
21 Incorrect 132 ms 79632 KB Output isn't correct
22 Correct 194 ms 79552 KB Output is correct
23 Correct 94 ms 79380 KB Output is correct
24 Correct 90 ms 79312 KB Output is correct
25 Incorrect 134 ms 79408 KB Output isn't correct
26 Incorrect 127 ms 79300 KB Output isn't correct
27 Correct 196 ms 79540 KB Output is correct
28 Incorrect 80 ms 79348 KB Output isn't correct
29 Correct 184 ms 79612 KB Output is correct
30 Correct 169 ms 79528 KB Output is correct
31 Correct 104 ms 79300 KB Output is correct
32 Incorrect 107 ms 79344 KB Output isn't correct
33 Incorrect 83 ms 79300 KB Output isn't correct
34 Correct 143 ms 79552 KB Output is correct
35 Incorrect 86 ms 79348 KB Output isn't correct
36 Correct 207 ms 79556 KB Output is correct
37 Incorrect 94 ms 79684 KB Output isn't correct
38 Correct 161 ms 79368 KB Output is correct
39 Incorrect 94 ms 79556 KB Output isn't correct
40 Correct 141 ms 79364 KB Output is correct
41 Correct 121 ms 79520 KB Output is correct
42 Incorrect 166 ms 79476 KB Output isn't correct