| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 334273 | 2020-12-08T22:40:01 Z | Fischer | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 262148 KB |
#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[10 * maxn];
int nxt[10 * maxn];
int T = 0;
int cnt[maxn];
int dp[maxn];
int p[100010];
int main() {
int m, q;
scanf("%d%d", &m, &q);
memset(head, -1, sizeof head);
for (int i = 0; i < m; ++i) {
scanf("%d", p+i);
for (int j=p[i]; j<maxn; j+=p[i]) {
assert(T < 10 * maxn);
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 (front < i && cnt[front] == 0) front++;
if (front == i) dp[i] = mx;
else dp[i] = min(mx, dp[front] + 1);
}
while (q--) {
int n;
scanf("%d", &n);
if (dp[n] > n) puts("oo");
else printf("%d\n", dp[n]);
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 147 ms | 131820 KB | Output is correct |
| 2 | Correct | 253 ms | 198380 KB | Output is correct |
| 3 | Correct | 192 ms | 178284 KB | Output is correct |
| 4 | Correct | 126 ms | 123884 KB | Output is correct |
| 5 | Correct | 179 ms | 141164 KB | Output is correct |
| 6 | Correct | 147 ms | 131820 KB | Output is correct |
| 7 | Correct | 197 ms | 178284 KB | Output is correct |
| 8 | Correct | 236 ms | 204916 KB | Output is correct |
| 9 | Correct | 317 ms | 228228 KB | Output is correct |
| 10 | Correct | 361 ms | 240492 KB | Output is correct |
| 11 | Correct | 307 ms | 203116 KB | Output is correct |
| 12 | Correct | 118 ms | 122092 KB | Output is correct |
| 13 | Runtime error | 526 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 | Runtime error | 526 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 15 | Correct | 268 ms | 195968 KB | Output is correct |
| 16 | Correct | 248 ms | 198380 KB | Output is correct |
| 17 | Correct | 208 ms | 141420 KB | Output is correct |
| 18 | Correct | 125 ms | 123756 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 229 ms | 131436 KB | Output is correct |
| 2 | Correct | 257 ms | 136812 KB | Output is correct |
| 3 | Runtime error | 492 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 | Correct | 309 ms | 156268 KB | Output is correct |
| 5 | Correct | 728 ms | 228972 KB | Output is correct |
| 6 | Correct | 226 ms | 173932 KB | Output is correct |
| 7 | Correct | 226 ms | 131564 KB | Output is correct |
| 8 | Correct | 287 ms | 151944 KB | Output is correct |
| 9 | Correct | 931 ms | 245816 KB | Output is correct |
| 10 | Runtime error | 494 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 11 | Runtime error | 572 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 | Correct | 460 ms | 214636 KB | Output is correct |
| 13 | Correct | 173 ms | 138604 KB | Output is correct |
| 14 | Correct | 312 ms | 156256 KB | Output is correct |
| 15 | Runtime error | 755 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Correct | 260 ms | 136812 KB | Output is correct |
| 17 | Runtime error | 576 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 18 | Correct | 921 ms | 257516 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 681 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 | Runtime error | 526 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 | Runtime error | 487 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 4 | Correct | 520 ms | 225004 KB | Output is correct |
| 5 | Correct | 368 ms | 137068 KB | Output is correct |
| 6 | Runtime error | 736 ms | 262144 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 | Correct | 738 ms | 196332 KB | Output is correct |
| 8 | Runtime error | 672 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 | Runtime error | 681 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 | Correct | 606 ms | 208416 KB | Output is correct |
| 11 | Correct | 465 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 | Runtime error | 753 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 14 | Correct | 425 ms | 250476 KB | Output is correct |
| 15 | Runtime error | 585 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 16 | Runtime error | 557 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 17 | Correct | 887 ms | 236524 KB | Output is correct |
| 18 | Runtime error | 524 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 19 | Correct | 208 ms | 154476 KB | Output is correct |
| 20 | Runtime error | 486 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 21 | Runtime error | 450 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 22 | Runtime error | 574 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 23 | Correct | 401 ms | 140140 KB | Output is correct |
| 24 | Correct | 207 ms | 133484 KB | Output is correct |
| 25 | Correct | 602 ms | 223440 KB | Output is correct |
| 26 | Correct | 514 ms | 224876 KB | Output is correct |
| 27 | Runtime error | 427 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 28 | Correct | 216 ms | 149996 KB | Output is correct |
| 29 | Execution timed out | 1109 ms | 236524 KB | Time limit exceeded |
| 30 | Execution timed out | 1008 ms | 215020 KB | Time limit exceeded |
| 31 | Correct | 306 ms | 153964 KB | Output is correct |
| 32 | Correct | 372 ms | 165996 KB | Output is correct |
| 33 | Correct | 166 ms | 126836 KB | Output is correct |
| 34 | Correct | 744 ms | 196204 KB | Output is correct |
| 35 | Correct | 262 ms | 151916 KB | Output is correct |
| 36 | Runtime error | 592 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 37 | Correct | 393 ms | 137072 KB | Output is correct |
| 38 | Runtime error | 734 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
| 39 | Correct | 255 ms | 138220 KB | Output is correct |
| 40 | Correct | 696 ms | 243948 KB | Output is correct |
| 41 | Correct | 646 ms | 217100 KB | Output is correct |
| 42 | Runtime error | 516 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |