#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[maxn];
int nxt[maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m, q;
cin >> m >> q;
vector<int> p(m);
memset(head, -1, sizeof head);
for (int& x : p) {
cin >> x;
for (int j=x; j<maxn; j+=x) {
nxt[T] = head[j];
head[j] = T;
val[T] = j - x;
T++;
}
}
int front = 0;
cnt[0] = p.size();
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 |
144 ms |
131820 KB |
Output is correct |
| 2 |
Incorrect |
288 ms |
196076 KB |
Output isn't correct |
| 3 |
Correct |
214 ms |
178540 KB |
Output is correct |
| 4 |
Correct |
150 ms |
123884 KB |
Output is correct |
| 5 |
Correct |
184 ms |
141036 KB |
Output is correct |
| 6 |
Correct |
153 ms |
132048 KB |
Output is correct |
| 7 |
Correct |
214 ms |
178344 KB |
Output is correct |
| 8 |
Incorrect |
295 ms |
196076 KB |
Output isn't correct |
| 9 |
Incorrect |
494 ms |
196204 KB |
Output isn't correct |
| 10 |
Incorrect |
727 ms |
196332 KB |
Output isn't correct |
| 11 |
Incorrect |
430 ms |
196104 KB |
Output isn't correct |
| 12 |
Correct |
115 ms |
122092 KB |
Output is correct |
| 13 |
Runtime error |
377 ms |
238444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
385 ms |
238700 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Correct |
289 ms |
196028 KB |
Output is correct |
| 16 |
Incorrect |
294 ms |
196076 KB |
Output isn't correct |
| 17 |
Correct |
205 ms |
141420 KB |
Output is correct |
| 18 |
Correct |
123 ms |
123884 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
239 ms |
131564 KB |
Output is correct |
| 2 |
Correct |
257 ms |
137580 KB |
Output is correct |
| 3 |
Runtime error |
382 ms |
239104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Correct |
325 ms |
156420 KB |
Output is correct |
| 5 |
Execution timed out |
1103 ms |
177516 KB |
Time limit exceeded |
| 6 |
Correct |
242 ms |
174100 KB |
Output is correct |
| 7 |
Correct |
232 ms |
131564 KB |
Output is correct |
| 8 |
Correct |
287 ms |
152044 KB |
Output is correct |
| 9 |
Execution timed out |
1104 ms |
171500 KB |
Time limit exceeded |
| 10 |
Runtime error |
376 ms |
238956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
399 ms |
238816 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Incorrect |
865 ms |
196196 KB |
Output isn't correct |
| 13 |
Correct |
173 ms |
138604 KB |
Output is correct |
| 14 |
Correct |
322 ms |
156396 KB |
Output is correct |
| 15 |
Runtime error |
431 ms |
238828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Correct |
264 ms |
137708 KB |
Output is correct |
| 17 |
Runtime error |
391 ms |
238352 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Execution timed out |
1092 ms |
171756 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
394 ms |
238828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
389 ms |
239116 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
378 ms |
238828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Execution timed out |
1097 ms |
196972 KB |
Time limit exceeded |
| 5 |
Correct |
366 ms |
138552 KB |
Output is correct |
| 6 |
Execution timed out |
1098 ms |
175596 KB |
Time limit exceeded |
| 7 |
Correct |
754 ms |
197496 KB |
Output is correct |
| 8 |
Runtime error |
401 ms |
238956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
395 ms |
238828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Incorrect |
909 ms |
196344 KB |
Output isn't correct |
| 11 |
Correct |
483 ms |
184812 KB |
Output is correct |
| 12 |
Execution timed out |
1108 ms |
177900 KB |
Time limit exceeded |
| 13 |
Runtime error |
437 ms |
238668 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Incorrect |
880 ms |
196976 KB |
Output isn't correct |
| 15 |
Runtime error |
382 ms |
238444 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
386 ms |
238572 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Execution timed out |
1097 ms |
171332 KB |
Time limit exceeded |
| 18 |
Runtime error |
385 ms |
238956 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Correct |
220 ms |
154604 KB |
Output is correct |
| 20 |
Runtime error |
384 ms |
238828 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 21 |
Execution timed out |
1108 ms |
192204 KB |
Time limit exceeded |
| 22 |
Runtime error |
389 ms |
239212 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 23 |
Correct |
410 ms |
141036 KB |
Output is correct |
| 24 |
Correct |
203 ms |
134252 KB |
Output is correct |
| 25 |
Execution timed out |
1105 ms |
188876 KB |
Time limit exceeded |
| 26 |
Execution timed out |
1069 ms |
196204 KB |
Time limit exceeded |
| 27 |
Runtime error |
376 ms |
239340 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 28 |
Correct |
219 ms |
150892 KB |
Output is correct |
| 29 |
Execution timed out |
1102 ms |
170604 KB |
Time limit exceeded |
| 30 |
Execution timed out |
1103 ms |
188012 KB |
Time limit exceeded |
| 31 |
Correct |
313 ms |
154656 KB |
Output is correct |
| 32 |
Correct |
369 ms |
166508 KB |
Output is correct |
| 33 |
Correct |
166 ms |
127340 KB |
Output is correct |
| 34 |
Correct |
740 ms |
197356 KB |
Output is correct |
| 35 |
Correct |
266 ms |
152812 KB |
Output is correct |
| 36 |
Runtime error |
386 ms |
239084 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 37 |
Correct |
370 ms |
138732 KB |
Output is correct |
| 38 |
Execution timed out |
1078 ms |
175212 KB |
Time limit exceeded |
| 39 |
Correct |
266 ms |
139116 KB |
Output is correct |
| 40 |
Execution timed out |
1099 ms |
174828 KB |
Time limit exceeded |
| 41 |
Execution timed out |
1012 ms |
197812 KB |
Time limit exceeded |
| 42 |
Runtime error |
376 ms |
238572 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
