oj.uz

Submission #447944

# Submission time Handle Problem Language Result Execution time Memory
447944 2021-07-28T08:52:04 Z prvocislo Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 888 ms 123724 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 1e7 + 5, inf = 1e9 + 5;
void chmin(int &a, const int &b) { a = min(a, b); }
void chmax(int &a, const int &b) { a = max(a, b); }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> lp(maxn, -1), pr;
    for (int i = 2; i < maxn; i++)
    {
        if (lp[i] == -1) pr.push_back(i), lp[i] = i;
        for (int j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] < maxn; j++) 
            lp[i*pr[j]] = pr[j];
    }
    int m, q;
    cin >> m >> q;
    vector<int> p(m);
    vector<bool> b(maxn, false);
    int mul = 1;
    for (int i = 0; i < m; i++)
    {
        cin >> p[i];
        if (mul * 1ll * p[i] < (ll)maxn) mul *= p[i];
        else mul = maxn;
        b[p[i]] = true;
    }
    vector<int> dp(maxn, inf), hr(maxn+1, 0);
    for (int i = 0; i < mul; i++)
    {
        if (!i) dp[i] = 0;
        else
        {
            if (i <= hr[dp[i-1]]) dp[i] = dp[i-1];
            else dp[i] = dp[i-1]+1;
        }
        int big = 1;
        if (!i) big = p.back();
        for (int j = i; j > 1; j /= lp[j])
            if (b[lp[j]]) chmax(big, lp[j]);
        if (big != 1)
        {
            chmax(hr[dp[i]+1], i+big-1);
        }
    }
    while (q--)
    {
        int n; cin >> n;
        if (dp[n] == inf) cout << "oo\n";
        else cout << dp[n] << "\n";
    }
    return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 121620 KB Output is correct
2 Correct 783 ms 121568 KB Output is correct
3 Correct 196 ms 121472 KB Output is correct
4 Correct 728 ms 121656 KB Output is correct
5 Correct 751 ms 121564 KB Output is correct
6 Correct 172 ms 121532 KB Output is correct
7 Correct 188 ms 121516 KB Output is correct
8 Correct 225 ms 121500 KB Output is correct
9 Correct 758 ms 121588 KB Output is correct
10 Correct 779 ms 121568 KB Output is correct
11 Correct 796 ms 121568 KB Output is correct
12 Correct 729 ms 121652 KB Output is correct
13 Correct 759 ms 121648 KB Output is correct
14 Correct 739 ms 121696 KB Output is correct
15 Correct 778 ms 121556 KB Output is correct
16 Correct 801 ms 121528 KB Output is correct
17 Correct 731 ms 121524 KB Output is correct
18 Correct 725 ms 121680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 708 ms 121720 KB Output is correct
2 Correct 726 ms 122724 KB Output is correct
3 Correct 706 ms 122312 KB Output is correct
4 Correct 740 ms 121492 KB Output is correct
5 Correct 870 ms 122124 KB Output is correct
6 Correct 787 ms 121568 KB Output is correct
7 Correct 724 ms 121748 KB Output is correct
8 Correct 735 ms 121660 KB Output is correct
9 Correct 851 ms 122348 KB Output is correct
10 Correct 771 ms 122340 KB Output is correct
11 Correct 745 ms 121996 KB Output is correct
12 Correct 835 ms 121584 KB Output is correct
13 Correct 727 ms 121596 KB Output is correct
14 Correct 753 ms 121596 KB Output is correct
15 Correct 809 ms 122008 KB Output is correct
16 Correct 729 ms 122628 KB Output is correct
17 Correct 744 ms 121596 KB Output is correct
18 Correct 837 ms 122672 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 122384 KB Output is correct
2 Correct 752 ms 122264 KB Output is correct
3 Correct 723 ms 122636 KB Output is correct
4 Correct 875 ms 122496 KB Output is correct
5 Correct 748 ms 123676 KB Output is correct
6 Correct 839 ms 122600 KB Output is correct
7 Correct 800 ms 123216 KB Output is correct
8 Correct 764 ms 122384 KB Output is correct
9 Correct 780 ms 122420 KB Output is correct
10 Correct 809 ms 121700 KB Output is correct
11 Correct 785 ms 121848 KB Output is correct
12 Correct 834 ms 121824 KB Output is correct
13 Correct 776 ms 122820 KB Output is correct
14 Correct 757 ms 122764 KB Output is correct
15 Correct 746 ms 121780 KB Output is correct
16 Correct 742 ms 121904 KB Output is correct
17 Correct 858 ms 122352 KB Output is correct
18 Correct 731 ms 122332 KB Output is correct
19 Correct 757 ms 121792 KB Output is correct
20 Correct 719 ms 122640 KB Output is correct
21 Correct 754 ms 122964 KB Output is correct
22 Correct 767 ms 123628 KB Output is correct
23 Correct 758 ms 122820 KB Output is correct
24 Correct 756 ms 122492 KB Output is correct
25 Correct 881 ms 122536 KB Output is correct
26 Correct 862 ms 122544 KB Output is correct
27 Correct 703 ms 123160 KB Output is correct
28 Correct 755 ms 122680 KB Output is correct
29 Correct 796 ms 123604 KB Output is correct
30 Correct 788 ms 123224 KB Output is correct
31 Correct 762 ms 122568 KB Output is correct
32 Correct 783 ms 122460 KB Output is correct
33 Correct 731 ms 122476 KB Output is correct
34 Correct 797 ms 123224 KB Output is correct
35 Correct 763 ms 122588 KB Output is correct
36 Correct 773 ms 123512 KB Output is correct
37 Correct 758 ms 123724 KB Output is correct
38 Correct 837 ms 122740 KB Output is correct
39 Correct 738 ms 122644 KB Output is correct
40 Correct 888 ms 122616 KB Output is correct
41 Correct 856 ms 123212 KB Output is correct
42 Correct 731 ms 122708 KB Output is correct