Submission #1124140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124140		kustizus	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	100 / 100	863 ms	88024 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define sz(s) (int)s.size()
#define bit(i, j) ((j >> i) & 1)
#define all(v) v.begin(), v.end()
#define taskname "file"

typedef long long ll;

const int N = 1e7, M = 1e5;
int m, q, p[M + 5], dp[N + 5], u[N + 5];
bool cnt[N + 5];

void sangnt(){
    vector <int> v;
    for (int i = 2; i <= N; ++i){
        if (!u[i]){
            u[i] = i;
            v.push_back(i);
        }
        for (int j : v){
            if (i * j > N) break;
            u[i * j] = j;
            if (u[i * j] == u[i]) break;
        }
    }
}

void solve(){
    sangnt();
    cin >> m >> q;
    for (int i = 1; i <= m; ++i){
        cin >> p[i];
        cnt[p[i]] = true;
    }
    dp[0] = 0;
    int pos = 0, mx = 0;
    while (pos <= N){
        int gh = -1;
        for (int i = pos; i <= mx; ++i){
            int x = i;
            if (!x){
                for (int i = 1; i <= m; ++i) gh = max(gh, p[i] - 1);
            }
            else{
                int d = x;
                while (d > 1){
                    int uoc = u[d];
                    if (cnt[uoc]) gh = max(gh, x + uoc - 1);
                    d /= uoc;
                }
            }
        }
        if (pos > gh) break;
        if (gh > N) gh = N;
        for (int i = mx + 1; i <= gh; ++i)
            dp[i] = dp[pos] + 1;
        pos = mx + 1;
        mx = gh;
    }
    while (q--){
        int n;
        cin >> n;
        if (!n) cout << 0 << "\n";
        else if (dp[n]) cout << dp[n] << "\n";
        else cout << "oo\n";
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    // freopen(taskname".inp", "r", stdin);
    // freopen(taskname".out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60