oj.uz

Submission #711787

# Submission time Handle Problem Language Result Execution time Memory
711787 2023-03-17T13:49:03 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 131 ms 22200 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 = 2e9;
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 5 ms 3540 KB Output is correct
2 Correct 21 ms 5312 KB Output is correct
3 Correct 13 ms 4980 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 9 ms 3796 KB Output is correct
6 Correct 6 ms 3668 KB Output is correct
7 Correct 14 ms 5076 KB Output is correct
8 Correct 16 ms 5400 KB Output is correct
9 Correct 28 ms 5580 KB Output is correct
10 Correct 29 ms 5620 KB Output is correct
11 Correct 22 ms 5168 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 56 ms 6000 KB Output is correct
14 Correct 56 ms 6160 KB Output is correct
15 Correct 19 ms 5260 KB Output is correct
16 Correct 21 ms 5312 KB Output is correct
17 Correct 15 ms 3968 KB Output is correct
18 Correct 7 ms 3412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7344 KB Execution killed with signal 11
2 Runtime error 35 ms 15704 KB Execution killed with signal 11
3 Runtime error 41 ms 18684 KB Execution killed with signal 11
4 Runtime error 9 ms 8272 KB Execution killed with signal 11
5 Runtime error 28 ms 15568 KB Execution killed with signal 11
6 Incorrect 23 ms 5332 KB Output isn't correct
7 Runtime error 9 ms 7316 KB Execution killed with signal 11
8 Runtime error 9 ms 7668 KB Execution killed with signal 11
9 Runtime error 33 ms 18084 KB Execution killed with signal 11
10 Runtime error 131 ms 20160 KB Execution killed with signal 11
11 Runtime error 29 ms 15516 KB Execution killed with signal 11
12 Runtime error 11 ms 10364 KB Execution killed with signal 11
13 Runtime error 6 ms 6996 KB Execution killed with signal 11
14 Runtime error 8 ms 8168 KB Execution killed with signal 11
15 Runtime error 104 ms 17072 KB Execution killed with signal 6
16 Runtime error 31 ms 15684 KB Execution killed with signal 11
17 Runtime error 16 ms 11368 KB Execution killed with signal 11
18 Runtime error 43 ms 21068 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 16504 KB Execution killed with signal 11
2 Runtime error 32 ms 16936 KB Execution killed with signal 11
3 Runtime error 37 ms 16756 KB Execution killed with signal 11
4 Runtime error 14 ms 10836 KB Execution killed with signal 11
5 Runtime error 37 ms 16460 KB Execution killed with signal 11
6 Runtime error 16 ms 12116 KB Execution killed with signal 11
7 Runtime error 39 ms 19956 KB Execution killed with signal 11
8 Runtime error 34 ms 16452 KB Execution killed with signal 11
9 Runtime error 30 ms 16448 KB Execution killed with signal 11
10 Runtime error 13 ms 10880 KB Execution killed with signal 11
11 Runtime error 16 ms 9856 KB Execution killed with signal 11
12 Runtime error 18 ms 11792 KB Execution killed with signal 11
13 Runtime error 24 ms 14632 KB Execution killed with signal 11
14 Runtime error 12 ms 10708 KB Execution killed with signal 11
15 Runtime error 17 ms 11860 KB Execution killed with signal 11
16 Runtime error 17 ms 12296 KB Execution killed with signal 11
17 Runtime error 24 ms 15292 KB Execution killed with signal 11
18 Runtime error 29 ms 16992 KB Execution killed with signal 11
19 Runtime error 7 ms 8448 KB Execution killed with signal 11
20 Runtime error 29 ms 16836 KB Execution killed with signal 11
21 Runtime error 14 ms 10964 KB Execution killed with signal 11
22 Runtime error 45 ms 21836 KB Execution killed with signal 11
23 Runtime error 19 ms 9604 KB Execution killed with signal 11
24 Runtime error 6 ms 6484 KB Execution killed with signal 11
25 Runtime error 17 ms 10680 KB Execution killed with signal 11
26 Runtime error 20 ms 10780 KB Execution killed with signal 11
27 Runtime error 48 ms 22200 KB Execution killed with signal 11
28 Runtime error 7 ms 7600 KB Execution killed with signal 11
29 Runtime error 41 ms 21420 KB Execution killed with signal 11
30 Runtime error 44 ms 17992 KB Execution killed with signal 11
31 Runtime error 9 ms 8148 KB Execution killed with signal 11
32 Runtime error 12 ms 8788 KB Execution killed with signal 11
33 Runtime error 5 ms 5992 KB Execution killed with signal 11
34 Runtime error 41 ms 19956 KB Execution killed with signal 11
35 Runtime error 7 ms 7892 KB Execution killed with signal 11
36 Runtime error 43 ms 20808 KB Execution killed with signal 11
37 Runtime error 39 ms 16460 KB Execution killed with signal 11
38 Runtime error 17 ms 12160 KB Execution killed with signal 11
39 Runtime error 7 ms 7040 KB Execution killed with signal 11
40 Runtime error 16 ms 11868 KB Execution killed with signal 11
41 Runtime error 42 ms 20684 KB Execution killed with signal 11
42 Runtime error 25 ms 11604 KB Execution killed with signal 11