Submission #923710

#	Time	Username	Problem	Language	Result	Execution time	Memory
923710		sleepntsheep	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	236 ms	80328 KiB

brunhilda

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);

const int N = 10000005;
int p[N], dp[N];
int m, q, x, mx;

int main()
{
    ShinLena;
    cin >> m >> q;
    for (int i = 0, x; i < m; ++i)
    {
        cin >> x;
        for (int i = 0; i < N; i += x) p[i] = max(p[i], x);
    }
    for (int l = 0, r = 0, ans = 0; l <= r and l < N; l = r + 1, r = min(N - 1, mx), ++ans)
        for (int i = l; i <= r; ++i) dp[i] = ans, mx = max(mx, i + p[i] - 1);
    for (int i = 0; i < q; ++i)
    {
        cin >> x;
        if (x > mx) cout << "oo\n";
        else cout << dp[x] << '\n';
    }
    return 0;
}


/*
#include <iostream>
#include <queue>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")

#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);

#if 1
#define M 100005
#define N 5000005
#else
#define M 20000
#define N 20000
#endif

int m, q, dp[N], yes[N], freq[N], i;

priority_queue<int, vector<int>, greater<int>> pq;

int si[4000];
vector<int> prime;

struct Precalc {
    unsigned char divisor[1<<16];


    constexpr Precalc() : divisor{} {
        for (int i = 0; i < (1<<16); i++)
            divisor[i] = 1;
        for (int i = 2; i * i < (1<<16); i++)
            if (divisor[i] == 1)
                for (int k = i * i; k < (1<<16); k += i)
                    divisor[k] = i;
    }
};

auto push = [](int x){
    pq.push(x);
};

auto del = [](int x){
    ++freq[x];
};

auto top = [](){
    while (pq.size())
    {
        int top = pq.top();
        if (freq[top]) --freq[top], pq.pop();
        else return top;
    }
    return int(1e9);
};


int main()
{
    for (int i = 2; i < 4000; ++i)
    {
        if (si[i]) continue;
        for (int j = 2 * i; j < 4000; j += i) si[j] = 1;
    }
    for (int i = 2; i < 4000; ++i) if (!si[i]) prime.push_back(i);

    memset(dp, 63, sizeof dp);
    ShinLena;

    dp[0] = 0;
    cin >> m >> q;
    for (int p, i = 1; i <= m; ++i)
    {
        cin >> p;
        yes[p] = 1;
    }

    constexpr Precalc P{};

    auto f = +[](int d){};
    decltype(f) ff = nullptr;

    auto factorize2 = [&](int n) {
        using u64 = unsigned long long;
        auto find_factor = [&](u64 n){
            if (n < (1 << 16)) return u64(P.divisor[n]);
            for (u64 d : prime)
                if (d * n < d)
                    return u64(-1) / d + 1;
            return 1ull;
        };

        u64 d;
        do {
            d = find_factor(n);
            if (yes[d]) ff(int(d));
            n /= d;
        } while (d != 1);
    };


    ff = +[](volatile int x){};
    for (int i = 1; i < N; ++i) factorize2(i);
    return 0;

    for (int i = 0; i < m; ++i) push(0);

    for (i = 1; i < N; ++i)
    {
        ff = +[](int x) { if(dp[i-x] < N) del(dp[i-x]); };
        factorize2(i);
    
        dp[i] = min(dp[i], top() + 1);

        if (dp[i] < 1e9)
        {
            ff = +push;
            factorize2(i);
        }
    }

    for (int x, i = 1; i <= q; ++i)
    {
        cin >> x;
        if (dp[x] >= 1e9) cout << "oo\n";
        else cout << dp[x] << '\n';
    }


    return 0;
}
*/

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