Submission #1142992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142992		Rainmaker2627	Brunhilda’s Birthday (BOI13_brunhilda)	C++20	0 / 100	338 ms	327680 KiB

brunhilda

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

struct lpq {
    priority_queue<int> a, b;
    void push(int x) { a.push(-x); }
    void pop(int x) { b.push(-x); }
    int top() {
        while (!b.empty() && a.top()==b.top()) {
            a.pop(); b.pop();
        } return (a.empty()?-2:-a.top());
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n=1e7, m, q;
    cin >> m >> q;
    vector<int> pr(m);
    for (int i = 0; i < m; i++) {
        cin >> pr[i];
    }
    
    lpq pq;
    vector<int> dp(n+1, -1);
    vector<vector<int>> sieve(n+1, vector<int>());
    for (int i = 0; i < m; i++) {
        pq.push(0);
        int p=pr[i];
        for (int j = p; j <= n; j+=p) {
            sieve[j].push_back(p);
        }
    }

    dp[0]=0;
    for (int i = 1; i <= n; i++) {
        for (auto p : sieve[i]) pq.pop(dp[i-p]);
        dp[i]=pq.top()+1;
        if (dp[i]==-1) continue;
        for (auto p : sieve[i]) pq.push(dp[i]);
    }
    
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        if (dp[x]==-1) cout << "oo\n";
        else cout << dp[x] << '\n';
    }

    return 0;
}

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