#include <bits/stdc++.h>
#define rep(x, y, z) for (int x = y; x < z; ++x)
#define reo(x, y) for (int x = 0; x < y; ++x)
using namespace std;
const int maxn = 1e7 + 10;
int head[maxn];
int val[2 * maxn];
int nxt[2 * maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
int p[100010];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, q;
cin >> m >> q;
memset(head, -1, sizeof head);
for (int i = 0; i < m; ++i) {
cin >> p[i];
for (int j=p[i]; j<maxn; j+=p[i]) {
nxt[T] = head[j];
head[j] = T;
val[T] = j - p[i];
T++;
}
}
int front = 0;
cnt[0] = m;
const int mx = 1e9;
for (int i = 1; i < maxn; ++i) {
for (int x = head[i]; ~x; x = nxt[x]) {
cnt[i]++;
cnt[val[x]]--;
}
while (cnt[front] == 0) front++;
if (front == i) dp[i] = mx;
else dp[i] = min(mx, dp[front] + 1);
}
while (q--) {
int n;
cin >> n;
if (dp[n] > n) cout << "oo\n";
else cout << dp[n] << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
149 ms |
131820 KB |
Output is correct |
2 |
Correct |
248 ms |
198380 KB |
Output is correct |
3 |
Correct |
206 ms |
178284 KB |
Output is correct |
4 |
Correct |
129 ms |
123756 KB |
Output is correct |
5 |
Correct |
184 ms |
141036 KB |
Output is correct |
6 |
Correct |
154 ms |
131968 KB |
Output is correct |
7 |
Correct |
197 ms |
178284 KB |
Output is correct |
8 |
Correct |
246 ms |
204908 KB |
Output is correct |
9 |
Correct |
317 ms |
228332 KB |
Output is correct |
10 |
Correct |
365 ms |
240620 KB |
Output is correct |
11 |
Correct |
313 ms |
203116 KB |
Output is correct |
12 |
Correct |
122 ms |
122092 KB |
Output is correct |
13 |
Execution timed out |
1103 ms |
258924 KB |
Time limit exceeded |
14 |
Execution timed out |
1110 ms |
260048 KB |
Time limit exceeded |
15 |
Correct |
272 ms |
196076 KB |
Output is correct |
16 |
Correct |
253 ms |
198380 KB |
Output is correct |
17 |
Correct |
214 ms |
141548 KB |
Output is correct |
18 |
Correct |
127 ms |
123756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
253 ms |
131440 KB |
Output is correct |
2 |
Correct |
277 ms |
136836 KB |
Output is correct |
3 |
Execution timed out |
1112 ms |
248172 KB |
Time limit exceeded |
4 |
Correct |
325 ms |
156332 KB |
Output is correct |
5 |
Correct |
820 ms |
229080 KB |
Output is correct |
6 |
Correct |
232 ms |
174060 KB |
Output is correct |
7 |
Correct |
227 ms |
131564 KB |
Output is correct |
8 |
Correct |
285 ms |
152044 KB |
Output is correct |
9 |
Correct |
956 ms |
246036 KB |
Output is correct |
10 |
Execution timed out |
1118 ms |
248172 KB |
Time limit exceeded |
11 |
Execution timed out |
1115 ms |
248044 KB |
Time limit exceeded |
12 |
Correct |
460 ms |
214636 KB |
Output is correct |
13 |
Correct |
175 ms |
138604 KB |
Output is correct |
14 |
Correct |
317 ms |
156312 KB |
Output is correct |
15 |
Runtime error |
892 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
16 |
Correct |
256 ms |
136940 KB |
Output is correct |
17 |
Execution timed out |
1119 ms |
255340 KB |
Time limit exceeded |
18 |
Correct |
937 ms |
257516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1099 ms |
262144 KB |
Time limit exceeded |
2 |
Execution timed out |
1093 ms |
247216 KB |
Time limit exceeded |
3 |
Execution timed out |
1120 ms |
247788 KB |
Time limit exceeded |
4 |
Correct |
515 ms |
224976 KB |
Output is correct |
5 |
Correct |
367 ms |
137068 KB |
Output is correct |
6 |
Runtime error |
751 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
7 |
Correct |
727 ms |
196332 KB |
Output is correct |
8 |
Execution timed out |
1063 ms |
262148 KB |
Time limit exceeded |
9 |
Execution timed out |
1080 ms |
262148 KB |
Time limit exceeded |
10 |
Correct |
615 ms |
208448 KB |
Output is correct |
11 |
Correct |
472 ms |
184812 KB |
Output is correct |
12 |
Runtime error |
705 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
13 |
Execution timed out |
1113 ms |
236652 KB |
Time limit exceeded |
14 |
Correct |
418 ms |
250476 KB |
Output is correct |
15 |
Execution timed out |
1108 ms |
262148 KB |
Time limit exceeded |
16 |
Execution timed out |
1117 ms |
250152 KB |
Time limit exceeded |
17 |
Correct |
909 ms |
236568 KB |
Output is correct |
18 |
Execution timed out |
1121 ms |
248172 KB |
Time limit exceeded |
19 |
Correct |
212 ms |
154476 KB |
Output is correct |
20 |
Execution timed out |
1119 ms |
247916 KB |
Time limit exceeded |
21 |
Runtime error |
458 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
22 |
Execution timed out |
1121 ms |
249452 KB |
Time limit exceeded |
23 |
Correct |
405 ms |
140012 KB |
Output is correct |
24 |
Correct |
208 ms |
133484 KB |
Output is correct |
25 |
Correct |
596 ms |
224108 KB |
Output is correct |
26 |
Correct |
515 ms |
225516 KB |
Output is correct |
27 |
Execution timed out |
1084 ms |
237488 KB |
Time limit exceeded |
28 |
Correct |
224 ms |
149984 KB |
Output is correct |
29 |
Execution timed out |
1116 ms |
236396 KB |
Time limit exceeded |
30 |
Execution timed out |
1028 ms |
215916 KB |
Time limit exceeded |
31 |
Correct |
304 ms |
153964 KB |
Output is correct |
32 |
Correct |
358 ms |
165868 KB |
Output is correct |
33 |
Correct |
172 ms |
126712 KB |
Output is correct |
34 |
Correct |
741 ms |
196312 KB |
Output is correct |
35 |
Correct |
259 ms |
152044 KB |
Output is correct |
36 |
Execution timed out |
1113 ms |
250092 KB |
Time limit exceeded |
37 |
Correct |
363 ms |
137068 KB |
Output is correct |
38 |
Runtime error |
748 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
39 |
Correct |
252 ms |
138348 KB |
Output is correct |
40 |
Correct |
716 ms |
244588 KB |
Output is correct |
41 |
Correct |
630 ms |
217324 KB |
Output is correct |
42 |
Execution timed out |
1118 ms |
251500 KB |
Time limit exceeded |