oj.uz

Submission #712206

# Submission time Handle Problem Language Result Execution time Memory
712206 2023-03-18T11:41:52 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 92 ms 21932 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 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;
    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 <= 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(s.find(koji[j]));
        }
        if (!s.empty()) dp[i] = *(s.begin()) + 1;
        ans[idx[i]] = dp[i];
        for (int j : primes[i]) {
            koji[j] = dp[i];
            s.insert(koji[j]);
        }
    }
    for (int i = 1; i <= q; i++) {
        if (ans[i] >= inf) cout << "oo" << en;
        else cout << ans[i] << en;
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3576 KB Output is correct
2 Correct 19 ms 5288 KB Output is correct
3 Correct 10 ms 4972 KB Output is correct
4 Correct 6 ms 3448 KB Output is correct
5 Correct 8 ms 3828 KB Output is correct
6 Correct 6 ms 3540 KB Output is correct
7 Correct 12 ms 4976 KB Output is correct
8 Correct 13 ms 5460 KB Output is correct
9 Correct 19 ms 5588 KB Output is correct
10 Correct 21 ms 5716 KB Output is correct
11 Correct 17 ms 5172 KB Output is correct
12 Correct 4 ms 3184 KB Output is correct
13 Correct 44 ms 6076 KB Output is correct
14 Correct 45 ms 6120 KB Output is correct
15 Correct 17 ms 5228 KB Output is correct
16 Correct 24 ms 5360 KB Output is correct
17 Correct 12 ms 4000 KB Output is correct
18 Correct 7 ms 3360 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 7272 KB Execution killed with signal 11
2 Runtime error 32 ms 15732 KB Execution killed with signal 11
3 Runtime error 35 ms 18576 KB Execution killed with signal 11
4 Runtime error 7 ms 8148 KB Execution killed with signal 11
5 Runtime error 29 ms 15576 KB Execution killed with signal 11
6 Runtime error 11 ms 9172 KB Execution killed with signal 11
7 Runtime error 11 ms 7284 KB Execution killed with signal 11
8 Runtime error 8 ms 7696 KB Execution killed with signal 11
9 Runtime error 33 ms 18060 KB Execution killed with signal 11
10 Runtime error 37 ms 18636 KB Execution killed with signal 11
11 Runtime error 27 ms 15532 KB Execution killed with signal 11
12 Runtime error 14 ms 10356 KB Execution killed with signal 11
13 Runtime error 7 ms 6996 KB Execution killed with signal 11
14 Runtime error 7 ms 8148 KB Execution killed with signal 11
15 Runtime error 32 ms 15436 KB Execution killed with signal 11
16 Runtime error 44 ms 17228 KB Execution killed with signal 11
17 Runtime error 20 ms 11492 KB Execution killed with signal 11
18 Runtime error 44 ms 20964 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 16468 KB Execution killed with signal 11
2 Runtime error 34 ms 16968 KB Execution killed with signal 11
3 Runtime error 92 ms 18768 KB Execution killed with signal 6
4 Runtime error 13 ms 10808 KB Execution killed with signal 11
5 Runtime error 40 ms 16596 KB Execution killed with signal 11
6 Runtime error 17 ms 12108 KB Execution killed with signal 11
7 Runtime error 82 ms 21904 KB Execution killed with signal 11
8 Runtime error 32 ms 16408 KB Execution killed with signal 11
9 Runtime error 33 ms 16524 KB Execution killed with signal 11
10 Runtime error 12 ms 10836 KB Execution killed with signal 11
11 Runtime error 10 ms 9940 KB Execution killed with signal 11
12 Runtime error 16 ms 11732 KB Execution killed with signal 11
13 Runtime error 24 ms 14624 KB Execution killed with signal 11
14 Runtime error 11 ms 10752 KB Execution killed with signal 11
15 Runtime error 21 ms 11884 KB Execution killed with signal 11
16 Runtime error 18 ms 12216 KB Execution killed with signal 11
17 Runtime error 25 ms 15348 KB Execution killed with signal 11
18 Runtime error 31 ms 17028 KB Execution killed with signal 11
19 Runtime error 8 ms 8404 KB Execution killed with signal 11
20 Runtime error 37 ms 16784 KB Execution killed with signal 11
21 Runtime error 13 ms 10964 KB Execution killed with signal 11
22 Runtime error 45 ms 21580 KB Execution killed with signal 11
23 Runtime error 13 ms 9684 KB Execution killed with signal 11
24 Runtime error 6 ms 6528 KB Execution killed with signal 11
25 Runtime error 12 ms 10708 KB Execution killed with signal 11
26 Runtime error 13 ms 10840 KB Execution killed with signal 11
27 Runtime error 52 ms 21932 KB Execution killed with signal 11
28 Runtime error 6 ms 7552 KB Execution killed with signal 11
29 Runtime error 45 ms 21224 KB Execution killed with signal 11
30 Runtime error 30 ms 18004 KB Execution killed with signal 11
31 Runtime error 8 ms 8148 KB Execution killed with signal 11
32 Runtime error 8 ms 8816 KB Execution killed with signal 11
33 Runtime error 5 ms 5972 KB Execution killed with signal 11
34 Runtime error 45 ms 19916 KB Execution killed with signal 11
35 Runtime error 7 ms 7892 KB Execution killed with signal 11
36 Runtime error 47 ms 20884 KB Execution killed with signal 11
37 Runtime error 36 ms 16112 KB Execution killed with signal 11
38 Runtime error 25 ms 12108 KB Execution killed with signal 11
39 Runtime error 7 ms 7080 KB Execution killed with signal 11
40 Runtime error 14 ms 11904 KB Execution killed with signal 11
41 Runtime error 40 ms 20612 KB Execution killed with signal 11
42 Runtime error 18 ms 11604 KB Execution killed with signal 11