Submission #923683

#	Time	Username	Problem	Language	Result	Execution time	Memory
923683		sleepntsheep	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	0 / 100	1101 ms	78680 KiB

brunhilda

#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 10000005
#else
#define M 20000
#define N 20000
#endif

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

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

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

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;
    }

    auto factorize = [&](int n) {
        vector<int> f, nf;
        for (int d : {2, 3, 5}) {
            if (n % d == 0) {
                f.push_back(d);
                n /= d;
                while (n % d == 0) n /= d;
            }
        }

        static array<int, 8> increments = {4, 2, 4, 2, 4, 6, 2, 6};
        int i = 0;

        for (long long d = 7; d * d <= n; d += increments[i++]) {
            if (n % d == 0) {
                f.push_back(d);
                n /= d;
                while (n % d == 0) n /= d;
            }
            if (i == 8) i = 0;
        }

        if (n > 1) f.push_back(n);

        return f;
    };

    auto factorize2 = [&](int n) {
        vector<int> f;
        for (auto d : prime) {
            if (d * d > n) break;
            if (n % d == 0)
            {
                f.push_back(d);
                n /= d;
                while (n % d == 0) n /=  d;
            }
        }

        if (n > 1) f.push_back(n);

        return f;
    };



    for (int i = 1; i < N; ++i) volatile auto F = factorize2(i);
    return 0;

    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);
    };

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

    for (int i = 1; i < N; ++i)
    {
        auto F = factorize(i);
        for (auto x : F) if (yes[x] and dp[i-x] < N)
            del(dp[i-x]);
    
        dp[i] = min(dp[i], top() + 1);

        if (dp[i] < 1e9)
            for (auto x : F) if (yes[x])
                push(dp[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: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60