oj.uz

Submission #558905

# Submission time Handle Problem Language Result Execution time Memory
558905 2022-05-08T23:59:31 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 56 ms 13164 KB 
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int M, Q; cin >> M >> Q;
    vector<int> p(M);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end()); 
    int mx = 100000;
    int res[mx];
    int lpf[mx];
    for (int i = 0; i < mx; i++) {
        lpf[i] = -1;
    }
    for (int j = 0; j < p.size(); j++) {
        for (int i = p[j]; i < mx; i += p[j]) {
            lpf[i] = j;
        }
    }
    int dp[M];
    multiset<int> ms;
    for (int i = 0; i < M; i++) {
        dp[i] = 0;
        ms.insert(dp[i]);
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        if (lpf[i] == -1) {
            ans = *ms.begin() + 1;
        } else {
            vector<int> invalid;
            int x = i;
            while (lpf[x] != -1) {
                if (dp[lpf[x]] == *ms.begin()) {
                    invalid.push_back(lpf[x]);
                    ms.erase(ms.find(dp[lpf[x]]));
                }
                int a = p[lpf[x]];
                while (x % a == 0) x /= a;
            }
            if (!ms.empty()) {
                ans = *ms.begin() + 1;
            }
            for (int j: invalid) {
                ms.insert(dp[j]);
            }
            for (int j: invalid) {
                if (j >= 0 && j < (int)p.size()) {
                    ms.erase(ms.find(dp[j]));
                    dp[j] = ans;
                    ms.insert(dp[j]);
                }
            }
        }
        res[i] = ans;
    }
    while (Q--) {
        int x;
        cin >> x;
        if (res[x] == (int)1e9) {
            cout << "oo\n";
        } else {
            cout << res[x] << '\n';
        }
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 980 KB Output isn't correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 8 ms 980 KB Output is correct
4 Correct 4 ms 1120 KB Output is correct
5 Correct 4 ms 980 KB Output is correct
6 Incorrect 3 ms 1108 KB Output isn't correct
7 Correct 6 ms 1092 KB Output is correct
8 Correct 8 ms 980 KB Output is correct
9 Correct 10 ms 1092 KB Output is correct
10 Correct 10 ms 980 KB Output is correct
11 Correct 8 ms 980 KB Output is correct
12 Correct 2 ms 980 KB Output is correct
13 Correct 11 ms 1152 KB Output is correct
14 Correct 12 ms 1152 KB Output is correct
15 Correct 7 ms 980 KB Output is correct
16 Correct 8 ms 1100 KB Output is correct
17 Correct 6 ms 1108 KB Output is correct
18 Correct 3 ms 1108 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 3284 KB Execution killed with signal 11
2 Runtime error 36 ms 12108 KB Execution killed with signal 11
3 Runtime error 34 ms 9724 KB Execution killed with signal 11
4 Runtime error 5 ms 2388 KB Execution killed with signal 11
5 Runtime error 23 ms 7636 KB Execution killed with signal 11
6 Runtime error 5 ms 2128 KB Execution killed with signal 11
7 Runtime error 6 ms 3284 KB Execution killed with signal 11
8 Runtime error 4 ms 2132 KB Execution killed with signal 11
9 Runtime error 42 ms 9860 KB Execution killed with signal 11
10 Runtime error 39 ms 9796 KB Execution killed with signal 11
11 Runtime error 30 ms 6416 KB Execution killed with signal 11
12 Runtime error 7 ms 2240 KB Execution killed with signal 11
13 Runtime error 3 ms 2260 KB Execution killed with signal 11
14 Runtime error 5 ms 2388 KB Execution killed with signal 11
15 Runtime error 25 ms 6604 KB Execution killed with signal 11
16 Runtime error 34 ms 12088 KB Execution killed with signal 11
17 Runtime error 12 ms 2260 KB Execution killed with signal 11
18 Runtime error 56 ms 13056 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 7500 KB Execution killed with signal 11
2 Runtime error 29 ms 7828 KB Execution killed with signal 11
3 Runtime error 27 ms 7508 KB Execution killed with signal 11
4 Runtime error 8 ms 2388 KB Execution killed with signal 11
5 Runtime error 37 ms 13012 KB Execution killed with signal 11
6 Runtime error 12 ms 2820 KB Execution killed with signal 11
7 Runtime error 38 ms 13164 KB Execution killed with signal 11
8 Runtime error 26 ms 7508 KB Execution killed with signal 11
9 Runtime error 25 ms 7508 KB Execution killed with signal 11
10 Runtime error 8 ms 2644 KB Execution killed with signal 11
11 Runtime error 6 ms 2496 KB Execution killed with signal 11
12 Runtime error 11 ms 2644 KB Execution killed with signal 11
13 Runtime error 21 ms 5352 KB Execution killed with signal 11
14 Runtime error 14 ms 1996 KB Execution killed with signal 11
15 Runtime error 14 ms 2644 KB Execution killed with signal 11
16 Runtime error 15 ms 2764 KB Execution killed with signal 11
17 Runtime error 23 ms 7024 KB Execution killed with signal 11
18 Runtime error 32 ms 7756 KB Execution killed with signal 11
19 Runtime error 5 ms 2516 KB Execution killed with signal 11
20 Runtime error 28 ms 7548 KB Execution killed with signal 11
21 Runtime error 11 ms 1996 KB Execution killed with signal 11
22 Runtime error 46 ms 13040 KB Execution killed with signal 11
23 Runtime error 12 ms 5332 KB Execution killed with signal 11
24 Runtime error 3 ms 2132 KB Execution killed with signal 11
25 Runtime error 8 ms 2260 KB Execution killed with signal 11
26 Runtime error 7 ms 2388 KB Execution killed with signal 11
27 Runtime error 46 ms 13116 KB Execution killed with signal 11
28 Runtime error 4 ms 2132 KB Execution killed with signal 11
29 Runtime error 47 ms 13112 KB Execution killed with signal 11
30 Runtime error 40 ms 9756 KB Execution killed with signal 11
31 Runtime error 5 ms 2516 KB Execution killed with signal 11
32 Runtime error 5 ms 2260 KB Execution killed with signal 11
33 Runtime error 2 ms 2132 KB Execution killed with signal 11
34 Runtime error 38 ms 13052 KB Execution killed with signal 11
35 Runtime error 4 ms 2260 KB Execution killed with signal 11
36 Runtime error 45 ms 11940 KB Execution killed with signal 11
37 Runtime error 34 ms 13004 KB Execution killed with signal 11
38 Runtime error 12 ms 2824 KB Execution killed with signal 11
39 Runtime error 4 ms 2260 KB Execution killed with signal 11
40 Runtime error 11 ms 3028 KB Execution killed with signal 11
41 Runtime error 47 ms 13132 KB Execution killed with signal 11
42 Runtime error 14 ms 2292 KB Execution killed with signal 11