oj.uz

Submission #558906

# Submission time Handle Problem Language Result Execution time Memory
558906 2022-05-08T23:59:50 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
55.2381 / 100
 1000 ms 84564 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 = 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: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
13.3333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 300 ms 78572 KB Output isn't correct
2 Correct 678 ms 78640 KB Output is correct
3 Correct 610 ms 78568 KB Output is correct
4 Correct 136 ms 78672 KB Output is correct
5 Correct 381 ms 78584 KB Output is correct
6 Incorrect 302 ms 78696 KB Output isn't correct
7 Correct 623 ms 78568 KB Output is correct
8 Correct 799 ms 78572 KB Output is correct
9 Execution timed out 1053 ms 78568 KB Time limit exceeded
10 Execution timed out 1008 ms 78576 KB Time limit exceeded
11 Correct 851 ms 78576 KB Output is correct
12 Correct 165 ms 78572 KB Output is correct
13 Execution timed out 1084 ms 78572 KB Time limit exceeded
14 Execution timed out 1067 ms 78584 KB Time limit exceeded
15 Correct 633 ms 78568 KB Output is correct
16 Correct 758 ms 78576 KB Output is correct
17 Correct 389 ms 78684 KB Output is correct
18 Correct 164 ms 78576 KB Output is correct

Subtask #2
13.3333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 79128 KB Output is correct
2 Correct 249 ms 83628 KB Output is correct
3 Execution timed out 1087 ms 82360 KB Time limit exceeded
4 Correct 303 ms 78744 KB Output is correct
5 Correct 808 ms 81424 KB Output is correct
6 Correct 411 ms 78640 KB Output is correct
7 Correct 164 ms 79232 KB Output is correct
8 Correct 290 ms 78624 KB Output is correct
9 Correct 988 ms 82448 KB Output is correct
10 Execution timed out 1092 ms 82316 KB Time limit exceeded
11 Execution timed out 1089 ms 80664 KB Time limit exceeded
12 Correct 690 ms 78696 KB Output is correct
13 Correct 141 ms 78616 KB Output is correct
14 Correct 307 ms 78748 KB Output is correct
15 Execution timed out 1097 ms 80776 KB Time limit exceeded
16 Correct 252 ms 83548 KB Output is correct
17 Execution timed out 1087 ms 78688 KB Time limit exceeded
18 Incorrect 806 ms 83968 KB Output isn't correct

Subtask #3
28.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 81212 KB Time limit exceeded
2 Execution timed out 1090 ms 81448 KB Time limit exceeded
3 Execution timed out 1092 ms 81208 KB Time limit exceeded
4 Correct 689 ms 79604 KB Output is correct
5 Correct 356 ms 84124 KB Output is correct
6 Execution timed out 1022 ms 79784 KB Time limit exceeded
7 Correct 743 ms 84564 KB Output is correct
8 Execution timed out 1093 ms 81212 KB Time limit exceeded
9 Execution timed out 1096 ms 81212 KB Time limit exceeded
10 Correct 633 ms 78896 KB Output is correct
11 Correct 510 ms 78948 KB Output is correct
12 Correct 961 ms 79020 KB Output is correct
13 Execution timed out 1092 ms 80224 KB Time limit exceeded
14 Execution timed out 1095 ms 78480 KB Time limit exceeded
15 Execution timed out 1088 ms 78804 KB Time limit exceeded
16 Execution timed out 1104 ms 78940 KB Time limit exceeded
17 Correct 961 ms 81044 KB Output is correct
18 Execution timed out 1080 ms 81356 KB Time limit exceeded
19 Correct 240 ms 78852 KB Output is correct
20 Execution timed out 1094 ms 81212 KB Time limit exceeded
21 Execution timed out 1099 ms 78572 KB Time limit exceeded
22 Execution timed out 1061 ms 84004 KB Time limit exceeded
23 Correct 359 ms 80348 KB Output is correct
24 Correct 172 ms 78892 KB Output is correct
25 Correct 746 ms 79664 KB Output is correct
26 Correct 767 ms 79524 KB Output is correct
27 Execution timed out 1088 ms 83968 KB Time limit exceeded
28 Incorrect 233 ms 78880 KB Output isn't correct
29 Execution timed out 1082 ms 83964 KB Time limit exceeded
30 Execution timed out 1022 ms 83268 KB Time limit exceeded
31 Correct 293 ms 78944 KB Output is correct
32 Correct 385 ms 79628 KB Output is correct
33 Correct 138 ms 78796 KB Output is correct
34 Correct 778 ms 84448 KB Output is correct
35 Incorrect 288 ms 78940 KB Output isn't correct
36 Execution timed out 1089 ms 83456 KB Time limit exceeded
37 Correct 369 ms 84128 KB Output is correct
38 Execution timed out 1089 ms 79404 KB Time limit exceeded
39 Correct 225 ms 78956 KB Output is correct
40 Correct 926 ms 79864 KB Output is correct
41 Correct 799 ms 84452 KB Output is correct
42 Execution timed out 1098 ms 78668 KB Time limit exceeded