| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 711982 | 2023-03-17T20:02:28 Z | stevancv | Brunhilda’s Birthday (BOI13_brunhilda) | C++14 | 1000 ms | 123312 KB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e6 + 2;
const int inf = 1e9;
vector<int> primes[M];
int idx[M], ans[N], koji[M], dp[M];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
multiset<pair<int, int>> s;
for (int i = 0; i < n; i++) {
int x; cin >> x;
s.insert({0, x});
for (int j = x; j < M; j += x) primes[j].push_back(x);
}
for (int i = 1; i <= q; i++) {
int x; cin >> x;
idx[x] = i;
}
for (int i = 1; i < M; i++) {
dp[i] = inf;
for (int j : primes[i]) {
s.erase({koji[j], j});
}
if (!s.empty()) dp[i] = s.begin()->first + 1;
if (idx[i] != 0) ans[idx[i]] = dp[i];
for (int j : primes[i]) {
s.insert({dp[i], j});
koji[j] = dp[i];
}
}
for (int i = 1; i <= q; i++) {
if (ans[i] >= inf) cout << "oo" << en;
else cout << ans[i] << en;
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 47 ms | 33024 KB | Output is correct |
| 2 | Correct | 216 ms | 50508 KB | Output is correct |
| 3 | Correct | 117 ms | 47284 KB | Output is correct |
| 4 | Correct | 57 ms | 30192 KB | Output is correct |
| 5 | Correct | 103 ms | 35972 KB | Output is correct |
| 6 | Correct | 50 ms | 33168 KB | Output is correct |
| 7 | Correct | 120 ms | 47332 KB | Output is correct |
| 8 | Correct | 174 ms | 51252 KB | Output is correct |
| 9 | Correct | 265 ms | 53364 KB | Output is correct |
| 10 | Correct | 432 ms | 54348 KB | Output is correct |
| 11 | Correct | 277 ms | 49728 KB | Output is correct |
| 12 | Correct | 48 ms | 29348 KB | Output is correct |
| 13 | Correct | 686 ms | 57312 KB | Output is correct |
| 14 | Correct | 775 ms | 57368 KB | Output is correct |
| 15 | Correct | 220 ms | 49736 KB | Output is correct |
| 16 | Correct | 211 ms | 50500 KB | Output is correct |
| 17 | Correct | 139 ms | 35964 KB | Output is correct |
| 18 | Correct | 52 ms | 30128 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 72 ms | 59764 KB | Execution killed with signal 11 |
| 2 | Runtime error | 92 ms | 70412 KB | Execution killed with signal 11 |
| 3 | Execution timed out | 1088 ms | 66592 KB | Time limit exceeded |
| 4 | Runtime error | 116 ms | 74892 KB | Execution killed with signal 11 |
| 5 | Runtime error | 430 ms | 110428 KB | Execution killed with signal 11 |
| 6 | Incorrect | 237 ms | 46860 KB | Output isn't correct |
| 7 | Runtime error | 87 ms | 59792 KB | Execution killed with signal 11 |
| 8 | Runtime error | 164 ms | 75588 KB | Execution killed with signal 11 |
| 9 | Runtime error | 406 ms | 116980 KB | Execution killed with signal 11 |
| 10 | Execution timed out | 1056 ms | 65256 KB | Time limit exceeded |
| 11 | Execution timed out | 1081 ms | 62128 KB | Time limit exceeded |
| 12 | Runtime error | 213 ms | 96924 KB | Execution killed with signal 11 |
| 13 | Runtime error | 56 ms | 63864 KB | Execution killed with signal 11 |
| 14 | Runtime error | 95 ms | 74764 KB | Execution killed with signal 11 |
| 15 | Runtime error | 596 ms | 118056 KB | Execution killed with signal 11 |
| 16 | Runtime error | 110 ms | 70368 KB | Execution killed with signal 11 |
| 17 | Runtime error | 299 ms | 107192 KB | Execution killed with signal 11 |
| 18 | Incorrect | 789 ms | 65464 KB | Output isn't correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 280 ms | 114548 KB | Execution killed with signal 11 |
| 2 | Runtime error | 377 ms | 116272 KB | Execution killed with signal 11 |
| 3 | Runtime error | 407 ms | 116104 KB | Execution killed with signal 11 |
| 4 | Runtime error | 173 ms | 99200 KB | Execution killed with signal 11 |
| 5 | Runtime error | 103 ms | 71156 KB | Execution killed with signal 11 |
| 6 | Runtime error | 276 ms | 105804 KB | Execution killed with signal 11 |
| 7 | Runtime error | 199 ms | 104488 KB | Execution killed with signal 11 |
| 8 | Runtime error | 297 ms | 114540 KB | Execution killed with signal 11 |
| 9 | Runtime error | 301 ms | 114536 KB | Execution killed with signal 11 |
| 10 | Runtime error | 191 ms | 94944 KB | Execution killed with signal 11 |
| 11 | Runtime error | 148 ms | 87672 KB | Execution killed with signal 11 |
| 12 | Runtime error | 273 ms | 104932 KB | Execution killed with signal 11 |
| 13 | Runtime error | 791 ms | 120524 KB | Execution killed with signal 11 |
| 14 | Runtime error | 396 ms | 110656 KB | Execution killed with signal 11 |
| 15 | Runtime error | 284 ms | 107732 KB | Execution killed with signal 11 |
| 16 | Runtime error | 327 ms | 108868 KB | Execution killed with signal 11 |
| 17 | Runtime error | 255 ms | 108488 KB | Execution killed with signal 11 |
| 18 | Runtime error | 426 ms | 116364 KB | Execution killed with signal 11 |
| 19 | Runtime error | 77 ms | 75344 KB | Execution killed with signal 11 |
| 20 | Runtime error | 367 ms | 116096 KB | Execution killed with signal 11 |
| 21 | Runtime error | 210 ms | 106068 KB | Execution killed with signal 11 |
| 22 | Runtime error | 348 ms | 121824 KB | Execution killed with signal 11 |
| 23 | Runtime error | 89 ms | 68344 KB | Execution killed with signal 11 |
| 24 | Runtime error | 71 ms | 59916 KB | Execution killed with signal 11 |
| 25 | Runtime error | 199 ms | 97384 KB | Execution killed with signal 11 |
| 26 | Runtime error | 208 ms | 99116 KB | Execution killed with signal 11 |
| 27 | Runtime error | 404 ms | 123312 KB | Execution killed with signal 11 |
| 28 | Runtime error | 79 ms | 70604 KB | Execution killed with signal 11 |
| 29 | Runtime error | 275 ms | 118188 KB | Execution killed with signal 11 |
| 30 | Runtime error | 244 ms | 113332 KB | Execution killed with signal 11 |
| 31 | Runtime error | 82 ms | 73056 KB | Execution killed with signal 11 |
| 32 | Runtime error | 134 ms | 79416 KB | Execution killed with signal 11 |
| 33 | Runtime error | 60 ms | 54964 KB | Execution killed with signal 11 |
| 34 | Runtime error | 212 ms | 104384 KB | Execution killed with signal 11 |
| 35 | Runtime error | 86 ms | 72208 KB | Execution killed with signal 11 |
| 36 | Runtime error | 394 ms | 120596 KB | Execution killed with signal 11 |
| 37 | Runtime error | 102 ms | 71228 KB | Execution killed with signal 11 |
| 38 | Runtime error | 259 ms | 105804 KB | Execution killed with signal 11 |
| 39 | Runtime error | 72 ms | 63660 KB | Execution killed with signal 11 |
| 40 | Runtime error | 231 ms | 103256 KB | Execution killed with signal 11 |
| 41 | Runtime error | 230 ms | 109104 KB | Execution killed with signal 11 |
| 42 | Runtime error | 294 ms | 108368 KB | Execution killed with signal 11 |