Submission #491820

#	Time	Username	Problem	Language	Result	Execution time	Memory
491820		Victor	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	294 ms	40556 KiB

brunhilda

    // #pragma GCC target ("avx,avx2,fma")
    // #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
    // #pragma GCC optimize ("unroll-loops")
    #include <bits/stdc++.h>
     
    using namespace std;
     
    #define rep(i, a, b) for (int i = (a); i < (b); ++i)
    #define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
    #define trav(a, x) for (auto &a : x)
     
    #define all(x) x.begin(), x.end()
    #define sz(x) x.size()
    #define pb push_back
    #define debug(x) cout << #x << " = " << x << endl
     
    #define umap unordered_map
    #define uset unordered_set
     
    typedef pair<int, int> ii;
    typedef pair<int, ii> iii;
    typedef vector<int> vi;
    typedef vector<ii> vii;
    typedef vector<vi> vvi;
     
    typedef long long ll;
    typedef pair<ll, ll> pll;
    typedef vector<ll> vll;
    typedef vector<pll> vpll;
     
    const int INF = 1'000'000'007;
     
    int n, q, ans[10'000'001], rem;
    priority_queue<ii> pq;
     
    int main() {
        cin.tie(0)->sync_with_stdio(0);
        cin.exceptions(cin.failbit);
     
        int p;
        ans[0] = 0;
     
        cin >> n >> q;
        rep(i, 0, n) {
            cin >> p;
            pq.emplace(0, p);
        }
     
        int val, prime;
        rep(i, 1, 10'000'001) {
            while (1) {
                tie(val, prime) = pq.top();
                val = -val;
     
                if (i / prime == val / prime) {
                    rem = i - val;
                    if (!rem)
                        ans[i] = INF;
                    else
                        ans[i] = ans[i - rem] + 1;
                    break;
     
                } else {
                    pq.pop();
                    pq.emplace(-(i - i % prime), prime);
                }
            }
        }
     
        while (q--) {
            cin >> val;
            if (ans[val] >= INF)
                cout << "oo" << '\n';
            else
                cout << ans[val] << '\n';
        }
        return 0;
    }

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