oj.uz

Submission #558910

# Submission time Handle Problem Language Result Execution time Memory
558910 2022-05-09T00:10:05 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 19 ms 4708 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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];
    }
    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];
    priority_queue<int, vector<int>, greater<int> > ms;
    for (int i = 0; i < M; i++) {
        dp[i] = 0;
        ms.push(dp[i]);
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        if (lpf[i] == -1) {
            ans = ms.top() + 1;
        } else {
            vector<int> invalid;
            int x = i;
            while (lpf[x] != -1) {
                if (dp[lpf[x]] == ms.top()) {
                    invalid.push_back(lpf[x]);
                    ms.pop();
                }
                int a = p[lpf[x]];
                while (x % a == 0) {
                    x /= a;
                }
            }
            if (!ms.empty()) {
                ans = ms.top() + 1;
            }
            for (int j: invalid) {
                dp[j] = ans;
                ms.push(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:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 980 KB Output isn't correct
2 Correct 5 ms 980 KB Output is correct
3 Correct 4 ms 980 KB Output is correct
4 Correct 3 ms 1108 KB Output is correct
5 Correct 2 ms 980 KB Output is correct
6 Incorrect 2 ms 1108 KB Output isn't correct
7 Correct 4 ms 1092 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 7 ms 980 KB Output is correct
10 Correct 7 ms 980 KB Output is correct
11 Correct 5 ms 1096 KB Output is correct
12 Correct 1 ms 980 KB Output is correct
13 Correct 8 ms 1108 KB Output is correct
14 Correct 12 ms 1108 KB Output is correct
15 Correct 5 ms 1092 KB Output is correct
16 Correct 5 ms 980 KB Output is correct
17 Correct 4 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 4 ms 2388 KB Execution killed with signal 11
2 Runtime error 11 ms 4400 KB Execution killed with signal 11
3 Runtime error 17 ms 3928 KB Execution killed with signal 11
4 Runtime error 4 ms 2132 KB Execution killed with signal 11
5 Runtime error 11 ms 3480 KB Execution killed with signal 11
6 Runtime error 5 ms 2004 KB Execution killed with signal 11
7 Runtime error 4 ms 2388 KB Execution killed with signal 11
8 Runtime error 3 ms 2004 KB Execution killed with signal 11
9 Runtime error 13 ms 3940 KB Execution killed with signal 11
10 Runtime error 15 ms 3924 KB Execution killed with signal 11
11 Runtime error 12 ms 3288 KB Execution killed with signal 11
12 Runtime error 6 ms 2004 KB Execution killed with signal 11
13 Runtime error 3 ms 2132 KB Execution killed with signal 11
14 Runtime error 3 ms 2132 KB Execution killed with signal 11
15 Runtime error 12 ms 3268 KB Execution killed with signal 11
16 Runtime error 11 ms 4408 KB Execution killed with signal 11
17 Runtime error 9 ms 2132 KB Execution killed with signal 11
18 Runtime error 17 ms 4692 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 3416 KB Execution killed with signal 11
2 Runtime error 13 ms 3484 KB Execution killed with signal 11
3 Runtime error 13 ms 3496 KB Execution killed with signal 11
4 Runtime error 6 ms 2132 KB Execution killed with signal 11
5 Runtime error 13 ms 4564 KB Execution killed with signal 11
6 Runtime error 8 ms 2260 KB Execution killed with signal 11
7 Runtime error 14 ms 4688 KB Execution killed with signal 11
8 Runtime error 13 ms 3488 KB Execution killed with signal 11
9 Runtime error 13 ms 3416 KB Execution killed with signal 11
10 Runtime error 6 ms 2260 KB Execution killed with signal 11
11 Runtime error 4 ms 2132 KB Execution killed with signal 11
12 Runtime error 9 ms 2132 KB Execution killed with signal 11
13 Runtime error 12 ms 3028 KB Execution killed with signal 11
14 Runtime error 9 ms 2004 KB Execution killed with signal 11
15 Runtime error 9 ms 2132 KB Execution killed with signal 11
16 Runtime error 9 ms 2248 KB Execution killed with signal 11
17 Runtime error 9 ms 3316 KB Execution killed with signal 11
18 Runtime error 15 ms 3500 KB Execution killed with signal 11
19 Runtime error 3 ms 2132 KB Execution killed with signal 11
20 Runtime error 14 ms 3416 KB Execution killed with signal 11
21 Runtime error 8 ms 1992 KB Execution killed with signal 11
22 Runtime error 17 ms 4692 KB Execution killed with signal 11
23 Runtime error 5 ms 3028 KB Execution killed with signal 11
24 Runtime error 3 ms 2004 KB Execution killed with signal 11
25 Runtime error 6 ms 2048 KB Execution killed with signal 11
26 Runtime error 6 ms 2132 KB Execution killed with signal 11
27 Runtime error 19 ms 4696 KB Execution killed with signal 11
28 Runtime error 3 ms 2004 KB Execution killed with signal 11
29 Runtime error 15 ms 4596 KB Execution killed with signal 11
30 Runtime error 12 ms 3936 KB Execution killed with signal 11
31 Runtime error 4 ms 2132 KB Execution killed with signal 11
32 Runtime error 4 ms 2132 KB Execution killed with signal 11
33 Runtime error 2 ms 2004 KB Execution killed with signal 11
34 Runtime error 13 ms 4708 KB Execution killed with signal 11
35 Runtime error 3 ms 2004 KB Execution killed with signal 11
36 Runtime error 17 ms 4428 KB Execution killed with signal 11
37 Runtime error 14 ms 4612 KB Execution killed with signal 11
38 Runtime error 8 ms 2260 KB Execution killed with signal 11
39 Runtime error 3 ms 2132 KB Execution killed with signal 11
40 Runtime error 7 ms 2284 KB Execution killed with signal 11
41 Runtime error 15 ms 4692 KB Execution killed with signal 11
42 Runtime error 9 ms 2052 KB Execution killed with signal 11