Submission #1124136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124136		kustizus	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	11.75 / 100	1105 ms	240172 KiB

brunhilda

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

#define int long long
#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[N + 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;
    deque <int> dq;
    dq.push_back(0);
    int pos = 1;
    while (pos <= N){
        int mx = -1;
        while (sz(dq)){
            int x = dq.back();
            dq.pop_back();
            if (!x){
                for (int i = 1; i <= m; ++i) mx = max(mx, p[i] - 1);
            }
            else{
                int d = x;
                while (d > 1){
                    int uoc = u[d];
                    if (!cnt[uoc]) break;
                    mx = max(mx, x + uoc - 1);
                    d /= uoc;
                }
            }
        }
        if (pos > mx) break;
        if (mx > N) mx = N;
        for (int i = pos; i <= mx; ++i){
            dq.push_back(i);
            dp[i] = dp[pos - 1] + 1;
        }
        pos = mx + 1;
    }
    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: 2.2222 / 20
• Subtask 2: 6.6667 / 20
• Subtask 3: 2.8571 / 60