oj.uz

Submission #558907

# Submission time Handle Problem Language Result Execution time Memory
558907 2022-05-09T00:00:33 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
59.8413 / 100
 1000 ms 84832 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];
    }
    int mx = 10000000;
    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:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
13.3333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 312 ms 78572 KB Output isn't correct
2 Correct 718 ms 78576 KB Output is correct
3 Correct 653 ms 78576 KB Output is correct
4 Correct 151 ms 78580 KB Output is correct
5 Correct 411 ms 78564 KB Output is correct
6 Incorrect 332 ms 78476 KB Output isn't correct
7 Correct 707 ms 78568 KB Output is correct
8 Correct 864 ms 78560 KB Output is correct
9 Execution timed out 1080 ms 78572 KB Time limit exceeded
10 Execution timed out 1070 ms 78548 KB Time limit exceeded
11 Correct 854 ms 78576 KB Output is correct
12 Correct 175 ms 78568 KB Output is correct
13 Execution timed out 1092 ms 78572 KB Time limit exceeded
14 Execution timed out 1086 ms 78620 KB Time limit exceeded
15 Correct 704 ms 78572 KB Output is correct
16 Correct 746 ms 78576 KB Output is correct
17 Correct 375 ms 78580 KB Output is correct
18 Correct 145 ms 78660 KB Output is correct

Subtask #2
12.2222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 79184 KB Output is correct
2 Correct 246 ms 83556 KB Output is correct
3 Execution timed out 1062 ms 82324 KB Time limit exceeded
4 Correct 313 ms 78668 KB Output is correct
5 Correct 849 ms 81360 KB Output is correct
6 Correct 418 ms 78636 KB Output is correct
7 Correct 173 ms 79128 KB Output is correct
8 Correct 316 ms 78628 KB Output is correct
9 Execution timed out 1084 ms 82372 KB Time limit exceeded
10 Execution timed out 1082 ms 82380 KB Time limit exceeded
11 Execution timed out 1096 ms 80664 KB Time limit exceeded
12 Correct 637 ms 78580 KB Output is correct
13 Correct 149 ms 78732 KB Output is correct
14 Correct 288 ms 78640 KB Output is correct
15 Execution timed out 1101 ms 80820 KB Time limit exceeded
16 Correct 240 ms 83496 KB Output is correct
17 Execution timed out 1087 ms 78740 KB Time limit exceeded
18 Incorrect 819 ms 83984 KB Output isn't correct

Subtask #3
34.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 81208 KB Time limit exceeded
2 Execution timed out 1095 ms 81456 KB Time limit exceeded
3 Execution timed out 1096 ms 81228 KB Time limit exceeded
4 Correct 663 ms 79016 KB Output is correct
5 Correct 329 ms 84256 KB Output is correct
6 Correct 940 ms 79276 KB Output is correct
7 Correct 676 ms 84100 KB Output is correct
8 Execution timed out 1095 ms 81216 KB Time limit exceeded
9 Execution timed out 1101 ms 81316 KB Time limit exceeded
10 Correct 588 ms 78896 KB Output is correct
11 Correct 448 ms 78852 KB Output is correct
12 Correct 906 ms 78884 KB Output is correct
13 Execution timed out 1096 ms 80096 KB Time limit exceeded
14 Execution timed out 1101 ms 78452 KB Time limit exceeded
15 Execution timed out 1062 ms 79004 KB Time limit exceeded
16 Execution timed out 1100 ms 78852 KB Time limit exceeded
17 Correct 831 ms 81048 KB Output is correct
18 Execution timed out 1098 ms 81356 KB Time limit exceeded
19 Correct 222 ms 78860 KB Output is correct
20 Execution timed out 1100 ms 81228 KB Time limit exceeded
21 Execution timed out 1051 ms 80004 KB Time limit exceeded
22 Execution timed out 1093 ms 83976 KB Time limit exceeded
23 Correct 318 ms 80364 KB Output is correct
24 Correct 163 ms 78836 KB Output is correct
25 Correct 666 ms 79096 KB Output is correct
26 Correct 677 ms 79020 KB Output is correct
27 Execution timed out 1101 ms 83964 KB Time limit exceeded
28 Incorrect 210 ms 78836 KB Output isn't correct
29 Correct 969 ms 84832 KB Output is correct
30 Correct 862 ms 82552 KB Output is correct
31 Correct 261 ms 78944 KB Output is correct
32 Correct 367 ms 79100 KB Output is correct
33 Correct 129 ms 78984 KB Output is correct
34 Correct 681 ms 84108 KB Output is correct
35 Incorrect 234 ms 78944 KB Output isn't correct
36 Execution timed out 1102 ms 83412 KB Time limit exceeded
37 Correct 327 ms 84160 KB Output is correct
38 Correct 958 ms 79636 KB Output is correct
39 Correct 200 ms 78956 KB Output is correct
40 Correct 803 ms 79356 KB Output is correct
41 Correct 659 ms 84172 KB Output is correct
42 Execution timed out 1099 ms 79176 KB Time limit exceeded