oj.uz

Submission #713401

# Submission time Handle Problem Language Result Execution time Memory
713401 2023-03-21T22:14:42 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 120 ms 23524 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 = 1e5 + 2;
const int inf = 1e9;
vector<int> primes[M];
int koji[M], dp[M];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        for (int j = x; j < M; j += x) primes[j].push_back(x);
    }
    multiset<int> s;
    for (int i = 0; i < n; i++) s.insert(0);
    for (int i = 1; i < M; i++) {
        dp[i] = inf;
        for (int j : primes[i]) {
            s.erase(s.find(koji[j]));
        }
        if (!s.empty()) dp[i] = *(s.begin()) + 1;
        for (int j : primes[i]) {
            koji[j] = dp[i];
            s.insert(koji[j]);
        }
    }
    for (int i = 1; i <= q; i++) {
        int x; cin >> x;
        if (dp[x] >= inf) cout << "oo" << en;
        else cout << dp[x] << en;
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3540 KB Output is correct
2 Correct 19 ms 5272 KB Output is correct
3 Correct 10 ms 4984 KB Output is correct
4 Correct 7 ms 3284 KB Output is correct
5 Correct 7 ms 3796 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 10 ms 4948 KB Output is correct
8 Correct 12 ms 5428 KB Output is correct
9 Correct 17 ms 5592 KB Output is correct
10 Correct 22 ms 5716 KB Output is correct
11 Correct 20 ms 5236 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 44 ms 5972 KB Output is correct
14 Correct 48 ms 6020 KB Output is correct
15 Correct 23 ms 5196 KB Output is correct
16 Correct 18 ms 5252 KB Output is correct
17 Correct 10 ms 3924 KB Output is correct
18 Correct 6 ms 3304 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 8816 KB Execution killed with signal 11
2 Runtime error 40 ms 17268 KB Execution killed with signal 11
3 Runtime error 96 ms 20152 KB Execution killed with signal 11
4 Runtime error 19 ms 9748 KB Execution killed with signal 11
5 Runtime error 55 ms 17096 KB Execution killed with signal 11
6 Runtime error 19 ms 10532 KB Execution killed with signal 11
7 Runtime error 12 ms 8936 KB Execution killed with signal 11
8 Runtime error 16 ms 8788 KB Execution killed with signal 11
9 Runtime error 69 ms 19720 KB Execution killed with signal 11
10 Runtime error 117 ms 20220 KB Execution killed with signal 11
11 Runtime error 94 ms 17128 KB Execution killed with signal 11
12 Runtime error 31 ms 11528 KB Execution killed with signal 11
13 Runtime error 12 ms 8532 KB Execution killed with signal 11
14 Runtime error 16 ms 9832 KB Execution killed with signal 11
15 Runtime error 77 ms 17040 KB Execution killed with signal 11
16 Runtime error 40 ms 17312 KB Execution killed with signal 11
17 Runtime error 52 ms 12480 KB Execution killed with signal 11
18 Runtime error 89 ms 22680 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 18048 KB Execution killed with signal 11
2 Runtime error 85 ms 18488 KB Execution killed with signal 11
3 Runtime error 87 ms 18336 KB Execution killed with signal 11
4 Runtime error 36 ms 12364 KB Execution killed with signal 11
5 Runtime error 44 ms 18048 KB Execution killed with signal 11
6 Runtime error 53 ms 13836 KB Execution killed with signal 11
7 Runtime error 60 ms 21492 KB Execution killed with signal 11
8 Runtime error 76 ms 18128 KB Execution killed with signal 11
9 Runtime error 81 ms 18056 KB Execution killed with signal 11
10 Runtime error 35 ms 12488 KB Execution killed with signal 11
11 Runtime error 29 ms 11384 KB Execution killed with signal 11
12 Runtime error 48 ms 13272 KB Execution killed with signal 11
13 Incorrect 74 ms 8944 KB Output isn't correct
14 Runtime error 31 ms 11548 KB Execution killed with signal 11
15 Runtime error 59 ms 13376 KB Execution killed with signal 11
16 Runtime error 65 ms 13736 KB Execution killed with signal 11
17 Runtime error 57 ms 16976 KB Execution killed with signal 11
18 Runtime error 86 ms 18568 KB Execution killed with signal 11
19 Runtime error 22 ms 10004 KB Execution killed with signal 11
20 Runtime error 97 ms 18376 KB Execution killed with signal 11
21 Runtime error 35 ms 11756 KB Execution killed with signal 11
22 Runtime error 107 ms 23360 KB Execution killed with signal 11
23 Runtime error 19 ms 11172 KB Execution killed with signal 11
24 Runtime error 11 ms 8032 KB Execution killed with signal 11
25 Runtime error 33 ms 11872 KB Execution killed with signal 11
26 Runtime error 40 ms 12392 KB Execution killed with signal 11
27 Runtime error 120 ms 23524 KB Execution killed with signal 11
28 Runtime error 14 ms 9172 KB Execution killed with signal 11
29 Runtime error 79 ms 23056 KB Execution killed with signal 11
30 Runtime error 55 ms 19588 KB Execution killed with signal 11
31 Runtime error 16 ms 9728 KB Execution killed with signal 11
32 Runtime error 20 ms 10244 KB Execution killed with signal 11
33 Runtime error 8 ms 7552 KB Execution killed with signal 11
34 Incorrect 70 ms 11516 KB Output isn't correct
35 Runtime error 15 ms 9428 KB Execution killed with signal 11
36 Runtime error 108 ms 22496 KB Execution killed with signal 11
37 Runtime error 39 ms 18064 KB Execution killed with signal 11
38 Runtime error 51 ms 13712 KB Execution killed with signal 11
39 Runtime error 13 ms 8632 KB Execution killed with signal 11
40 Runtime error 55 ms 13436 KB Execution killed with signal 11
41 Incorrect 84 ms 11772 KB Output isn't correct
42 Runtime error 58 ms 12580 KB Execution killed with signal 11