oj.uz

Submission #738529

# Submission time Handle Problem Language Result Execution time Memory
738529 2023-05-09T03:40:40 Z GrindMachine Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 824 ms 158632 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

ig i read the edi for this problem a long time ago (dont remember the approach in the edi tho)

greedy strategy
=> in each op, try to reduce the number as much as possible
because the #of ops is a montonic sequence

if we need k ops to make n1 = 0, then we would need <= k ops to make n2 = 0, n2 < n1
because we can apply the same k ops we applied to n1 to n2 and n2 would also become 0

i remember seeing this idea somewhere => maybe in the edi of this problem/some other problem

*/

const int MOD = 1e9 + 7;
const int N = 1e7 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<int> spf(N);

void precalc() {
    rep(i, N) spf[i] = i;
    for (int i = 2; i * i < N; ++i) {
        if (spf[i] != i) conts;
        for (int j = i * i; j < N; j += i) {
            amin(spf[j], i);
        }
    }
}

void solve(int test_case)
{
    precalc();

    int n, q; cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    vector<bool> there(N);
    rep(i, n) there[a[i]] = 1;

    vector<int> cnt(N);
    cnt[0] = n;

    vector<ll> dp(N, inf1);
    dp[0] = 0;
    int ptr = 0;

    rep1(i, N - 1) {
        int x = i;
        int prevp = -1;

        while (x > 1) {
            int p = spf[x];

            if (there[p] and p != prevp) {
                cnt[i - p]--;
                cnt[i]++;
            }

            x /= p;
            prevp = p;
        }

        while (ptr < N - 1 and !cnt[ptr]) {
            ptr++;
        }

        dp[i] = dp[ptr] + 1;
    }

    while (q--) {
        int m; cin >> m;
        if (dp[m] < inf1) cout << dp[m] << endl;
        else cout << "oo" << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 158116 KB Output is correct
2 Correct 681 ms 158104 KB Output is correct
3 Correct 685 ms 157984 KB Output is correct
4 Correct 597 ms 158096 KB Output is correct
5 Correct 630 ms 158012 KB Output is correct
6 Correct 622 ms 158100 KB Output is correct
7 Correct 652 ms 158028 KB Output is correct
8 Correct 700 ms 158092 KB Output is correct
9 Correct 700 ms 158104 KB Output is correct
10 Correct 727 ms 158096 KB Output is correct
11 Correct 719 ms 158100 KB Output is correct
12 Correct 609 ms 157976 KB Output is correct
13 Correct 747 ms 158112 KB Output is correct
14 Correct 756 ms 158108 KB Output is correct
15 Correct 685 ms 158096 KB Output is correct
16 Correct 677 ms 158100 KB Output is correct
17 Correct 611 ms 158104 KB Output is correct
18 Correct 628 ms 158100 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 158152 KB Output is correct
2 Correct 646 ms 158540 KB Output is correct
3 Correct 712 ms 158412 KB Output is correct
4 Correct 650 ms 158160 KB Output is correct
5 Correct 815 ms 158304 KB Output is correct
6 Correct 651 ms 158100 KB Output is correct
7 Correct 637 ms 158156 KB Output is correct
8 Correct 730 ms 158116 KB Output is correct
9 Correct 800 ms 158376 KB Output is correct
10 Correct 703 ms 158412 KB Output is correct
11 Correct 738 ms 158260 KB Output is correct
12 Correct 762 ms 158104 KB Output is correct
13 Correct 620 ms 158112 KB Output is correct
14 Correct 660 ms 158112 KB Output is correct
15 Correct 824 ms 158364 KB Output is correct
16 Correct 640 ms 158568 KB Output is correct
17 Correct 769 ms 158112 KB Output is correct
18 Correct 823 ms 158540 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 788 ms 158296 KB Output is correct
2 Correct 738 ms 158308 KB Output is correct
3 Correct 722 ms 158604 KB Output is correct
4 Correct 786 ms 158368 KB Output is correct
5 Correct 662 ms 158628 KB Output is correct
6 Correct 816 ms 158388 KB Output is correct
7 Correct 747 ms 158540 KB Output is correct
8 Correct 774 ms 158328 KB Output is correct
9 Correct 787 ms 158296 KB Output is correct
10 Correct 752 ms 158120 KB Output is correct
11 Correct 720 ms 158232 KB Output is correct
12 Correct 819 ms 158128 KB Output is correct
13 Correct 758 ms 158484 KB Output is correct
14 Correct 733 ms 158612 KB Output is correct
15 Correct 735 ms 158228 KB Output is correct
16 Correct 716 ms 158232 KB Output is correct
17 Correct 795 ms 158368 KB Output is correct
18 Correct 708 ms 158360 KB Output is correct
19 Correct 636 ms 158244 KB Output is correct
20 Correct 730 ms 158428 KB Output is correct
21 Correct 742 ms 158588 KB Output is correct
22 Correct 774 ms 158616 KB Output is correct
23 Correct 663 ms 158488 KB Output is correct
24 Correct 638 ms 158360 KB Output is correct
25 Correct 795 ms 158428 KB Output is correct
26 Correct 777 ms 158284 KB Output is correct
27 Correct 727 ms 158540 KB Output is correct
28 Correct 633 ms 158480 KB Output is correct
29 Correct 747 ms 158620 KB Output is correct
30 Correct 762 ms 158616 KB Output is correct
31 Correct 641 ms 158364 KB Output is correct
32 Correct 672 ms 158356 KB Output is correct
33 Correct 613 ms 158284 KB Output is correct
34 Correct 743 ms 158496 KB Output is correct
35 Correct 645 ms 158356 KB Output is correct
36 Correct 766 ms 158588 KB Output is correct
37 Correct 651 ms 158632 KB Output is correct
38 Correct 816 ms 158308 KB Output is correct
39 Correct 630 ms 158368 KB Output is correct
40 Correct 802 ms 158416 KB Output is correct
41 Correct 762 ms 158536 KB Output is correct
42 Correct 724 ms 158496 KB Output is correct