oj.uz

Submission #711794

# Submission time Handle Problem Language Result Execution time Memory
711794 2023-03-17T14:08:34 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 114 ms 22196 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;
    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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3540 KB Output is correct
2 Correct 21 ms 5336 KB Output is correct
3 Correct 11 ms 5076 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 8 ms 3796 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 13 ms 4976 KB Output is correct
8 Correct 16 ms 5460 KB Output is correct
9 Correct 24 ms 5708 KB Output is correct
10 Correct 30 ms 5752 KB Output is correct
11 Correct 26 ms 5240 KB Output is correct
12 Correct 5 ms 3156 KB Output is correct
13 Correct 57 ms 6008 KB Output is correct
14 Correct 82 ms 6092 KB Output is correct
15 Correct 19 ms 5320 KB Output is correct
16 Correct 22 ms 5320 KB Output is correct
17 Correct 13 ms 3972 KB Output is correct
18 Correct 6 ms 3412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7292 KB Execution killed with signal 11
2 Runtime error 34 ms 15296 KB Execution killed with signal 11
3 Runtime error 41 ms 18508 KB Execution killed with signal 11
4 Runtime error 9 ms 8176 KB Execution killed with signal 11
5 Runtime error 30 ms 15444 KB Execution killed with signal 11
6 Runtime error 9 ms 9172 KB Execution killed with signal 11
7 Runtime error 9 ms 7296 KB Execution killed with signal 11
8 Runtime error 8 ms 7764 KB Execution killed with signal 11
9 Runtime error 38 ms 17912 KB Execution killed with signal 11
10 Runtime error 40 ms 18472 KB Execution killed with signal 11
11 Runtime error 28 ms 15548 KB Execution killed with signal 11
12 Runtime error 13 ms 10328 KB Execution killed with signal 11
13 Runtime error 7 ms 6996 KB Execution killed with signal 11
14 Runtime error 8 ms 8148 KB Execution killed with signal 11
15 Runtime error 30 ms 15364 KB Execution killed with signal 11
16 Runtime error 36 ms 15324 KB Execution killed with signal 11
17 Runtime error 20 ms 11448 KB Execution killed with signal 11
18 Runtime error 96 ms 22196 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 16236 KB Execution killed with signal 11
2 Runtime error 32 ms 16848 KB Execution killed with signal 11
3 Runtime error 32 ms 16592 KB Execution killed with signal 11
4 Runtime error 13 ms 10836 KB Execution killed with signal 11
5 Runtime error 39 ms 15604 KB Execution killed with signal 11
6 Runtime error 19 ms 12112 KB Execution killed with signal 11
7 Runtime error 39 ms 19288 KB Execution killed with signal 11
8 Runtime error 33 ms 16180 KB Execution killed with signal 11
9 Runtime error 30 ms 16212 KB Execution killed with signal 11
10 Runtime error 16 ms 10836 KB Execution killed with signal 11
11 Runtime error 11 ms 9768 KB Execution killed with signal 11
12 Runtime error 15 ms 11732 KB Execution killed with signal 11
13 Runtime error 114 ms 18992 KB Execution killed with signal 6
14 Runtime error 15 ms 10708 KB Execution killed with signal 11
15 Runtime error 19 ms 11888 KB Execution killed with signal 11
16 Runtime error 19 ms 12244 KB Execution killed with signal 11
17 Runtime error 25 ms 15164 KB Execution killed with signal 11
18 Runtime error 31 ms 16796 KB Execution killed with signal 11
19 Runtime error 8 ms 8404 KB Execution killed with signal 11
20 Runtime error 32 ms 16584 KB Execution killed with signal 11
21 Runtime error 14 ms 10964 KB Execution killed with signal 11
22 Runtime error 44 ms 21272 KB Execution killed with signal 11
23 Runtime error 15 ms 9556 KB Execution killed with signal 11
24 Runtime error 7 ms 6484 KB Execution killed with signal 11
25 Runtime error 14 ms 10748 KB Execution killed with signal 11
26 Runtime error 14 ms 10884 KB Execution killed with signal 11
27 Runtime error 45 ms 21196 KB Execution killed with signal 11
28 Runtime error 7 ms 7636 KB Execution killed with signal 11
29 Runtime error 43 ms 20812 KB Execution killed with signal 11
30 Runtime error 30 ms 17528 KB Execution killed with signal 11
31 Runtime error 8 ms 8064 KB Execution killed with signal 11
32 Runtime error 11 ms 8788 KB Execution killed with signal 11
33 Runtime error 6 ms 5972 KB Execution killed with signal 11
34 Runtime error 44 ms 19348 KB Execution killed with signal 11
35 Runtime error 10 ms 7932 KB Execution killed with signal 11
36 Runtime error 57 ms 20224 KB Execution killed with signal 11
37 Runtime error 35 ms 15748 KB Execution killed with signal 11
38 Runtime error 18 ms 12232 KB Execution killed with signal 11
39 Runtime error 7 ms 7008 KB Execution killed with signal 11
40 Runtime error 15 ms 11944 KB Execution killed with signal 11
41 Runtime error 47 ms 20044 KB Execution killed with signal 11
42 Runtime error 18 ms 11592 KB Execution killed with signal 11