oj.uz

Submission #712227

# Submission time Handle Problem Language Result Execution time Memory
712227 2023-03-18T12:03:49 Z stevancv Brunhilda’s Birthday (BOI13_brunhilda) C++14
20 / 100
 72 ms 21980 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 3540 KB Output is correct
2 Correct 18 ms 5380 KB Output is correct
3 Correct 11 ms 4984 KB Output is correct
4 Correct 6 ms 3412 KB Output is correct
5 Correct 7 ms 3852 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 13 ms 4956 KB Output is correct
8 Correct 14 ms 5460 KB Output is correct
9 Correct 20 ms 5556 KB Output is correct
10 Correct 31 ms 5708 KB Output is correct
11 Correct 19 ms 5248 KB Output is correct
12 Correct 4 ms 3156 KB Output is correct
13 Correct 44 ms 5968 KB Output is correct
14 Correct 46 ms 6056 KB Output is correct
15 Correct 18 ms 5208 KB Output is correct
16 Correct 17 ms 5384 KB Output is correct
17 Correct 10 ms 4052 KB Output is correct
18 Correct 5 ms 3412 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 7228 KB Execution killed with signal 11
2 Runtime error 42 ms 15088 KB Execution killed with signal 11
3 Runtime error 50 ms 18632 KB Execution killed with signal 11
4 Runtime error 9 ms 8180 KB Execution killed with signal 11
5 Runtime error 68 ms 16848 KB Execution killed with signal 11
6 Runtime error 9 ms 9172 KB Execution killed with signal 11
7 Runtime error 8 ms 7220 KB Execution killed with signal 11
8 Runtime error 8 ms 7764 KB Execution killed with signal 11
9 Runtime error 34 ms 18028 KB Execution killed with signal 11
10 Runtime error 39 ms 18656 KB Execution killed with signal 11
11 Runtime error 33 ms 15532 KB Execution killed with signal 11
12 Runtime error 12 ms 10428 KB Execution killed with signal 11
13 Runtime error 7 ms 6996 KB Execution killed with signal 11
14 Runtime error 8 ms 8180 KB Execution killed with signal 11
15 Runtime error 28 ms 15444 KB Execution killed with signal 11
16 Runtime error 32 ms 15100 KB Execution killed with signal 11
17 Runtime error 15 ms 11400 KB Execution killed with signal 11
18 Runtime error 40 ms 21072 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 16520 KB Execution killed with signal 11
2 Runtime error 36 ms 17032 KB Execution killed with signal 11
3 Runtime error 31 ms 16792 KB Execution killed with signal 11
4 Runtime error 15 ms 10832 KB Execution killed with signal 11
5 Runtime error 44 ms 16296 KB Execution killed with signal 11
6 Runtime error 17 ms 12160 KB Execution killed with signal 11
7 Runtime error 72 ms 21256 KB Execution killed with signal 6
8 Runtime error 31 ms 16496 KB Execution killed with signal 11
9 Runtime error 37 ms 16460 KB Execution killed with signal 11
10 Runtime error 17 ms 10828 KB Execution killed with signal 11
11 Runtime error 15 ms 9812 KB Execution killed with signal 11
12 Runtime error 18 ms 11804 KB Execution killed with signal 11
13 Runtime error 30 ms 14640 KB Execution killed with signal 11
14 Runtime error 25 ms 11724 KB Execution killed with signal 6
15 Runtime error 16 ms 11860 KB Execution killed with signal 11
16 Runtime error 19 ms 12244 KB Execution killed with signal 11
17 Runtime error 30 ms 15308 KB Execution killed with signal 11
18 Runtime error 43 ms 17060 KB Execution killed with signal 11
19 Runtime error 8 ms 8420 KB Execution killed with signal 11
20 Runtime error 38 ms 17036 KB Execution killed with signal 11
21 Runtime error 13 ms 10932 KB Execution killed with signal 11
22 Runtime error 42 ms 21880 KB Execution killed with signal 11
23 Runtime error 14 ms 9368 KB Execution killed with signal 11
24 Runtime error 6 ms 6484 KB Execution killed with signal 11
25 Runtime error 12 ms 10708 KB Execution killed with signal 11
26 Runtime error 13 ms 10836 KB Execution killed with signal 11
27 Runtime error 49 ms 21980 KB Execution killed with signal 11
28 Runtime error 9 ms 7636 KB Execution killed with signal 11
29 Runtime error 46 ms 21408 KB Execution killed with signal 11
30 Runtime error 30 ms 17992 KB Execution killed with signal 11
31 Runtime error 7 ms 8148 KB Execution killed with signal 11
32 Runtime error 9 ms 8788 KB Execution killed with signal 11
33 Runtime error 5 ms 5972 KB Execution killed with signal 11
34 Runtime error 39 ms 19536 KB Execution killed with signal 11
35 Runtime error 7 ms 7892 KB Execution killed with signal 11
36 Runtime error 56 ms 20792 KB Execution killed with signal 11
37 Runtime error 38 ms 15396 KB Execution killed with signal 11
38 Runtime error 17 ms 12208 KB Execution killed with signal 11
39 Runtime error 8 ms 7036 KB Execution killed with signal 11
40 Runtime error 16 ms 11944 KB Execution killed with signal 11
41 Runtime error 39 ms 19620 KB Execution killed with signal 11
42 Runtime error 18 ms 11588 KB Execution killed with signal 11