oj.uz

Submission #923692

# Submission time Handle Problem Language Result Execution time Memory
923692 2024-02-07T15:15:57 Z sleepntsheep Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 1000 ms 40540 KB 
#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 {
            ff(int(d = find_factor(n)));
            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(yes[x] and dp[i-x] < N) del(dp[i-x]); };
        factorize2(i);
    
        dp[i] = min(dp[i], top() + 1);

        if (dp[i] < 1e9)
        {
            ff = +[](int x) { if(yes[x]) push(dp[i]); };
            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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 954 ms 22108 KB Output isn't correct
2 Incorrect 971 ms 22108 KB Output isn't correct
3 Incorrect 970 ms 22108 KB Output isn't correct
4 Incorrect 951 ms 22108 KB Output isn't correct
5 Incorrect 967 ms 22104 KB Output isn't correct
6 Incorrect 949 ms 22108 KB Output isn't correct
7 Incorrect 952 ms 22104 KB Output isn't correct
8 Incorrect 951 ms 22108 KB Output isn't correct
9 Incorrect 951 ms 22108 KB Output isn't correct
10 Incorrect 989 ms 22108 KB Output isn't correct
11 Incorrect 956 ms 22108 KB Output isn't correct
12 Incorrect 998 ms 22108 KB Output isn't correct
13 Execution timed out 1026 ms 22108 KB Time limit exceeded
14 Execution timed out 1030 ms 22104 KB Time limit exceeded
15 Incorrect 958 ms 22060 KB Output isn't correct
16 Incorrect 990 ms 22108 KB Output isn't correct
17 Incorrect 975 ms 22104 KB Output isn't correct
18 Execution timed out 1018 ms 22104 KB Time limit exceeded

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1006 ms 26200 KB Time limit exceeded
2 Execution timed out 1002 ms 40536 KB Time limit exceeded
3 Incorrect 987 ms 28252 KB Output isn't correct
4 Incorrect 975 ms 22108 KB Output isn't correct
5 Execution timed out 1030 ms 26312 KB Time limit exceeded
6 Incorrect 959 ms 22104 KB Output isn't correct
7 Execution timed out 1006 ms 26204 KB Time limit exceeded
8 Incorrect 978 ms 22104 KB Output isn't correct
9 Incorrect 995 ms 26204 KB Output isn't correct
10 Execution timed out 1048 ms 28252 KB Time limit exceeded
11 Execution timed out 1056 ms 26204 KB Time limit exceeded
12 Incorrect 994 ms 22104 KB Output isn't correct
13 Execution timed out 1008 ms 24152 KB Time limit exceeded
14 Incorrect 988 ms 22108 KB Output isn't correct
15 Incorrect 974 ms 26200 KB Output isn't correct
16 Execution timed out 1065 ms 40540 KB Time limit exceeded
17 Incorrect 983 ms 22108 KB Output isn't correct
18 Incorrect 983 ms 32348 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 983 ms 26200 KB Output isn't correct
2 Execution timed out 1052 ms 24156 KB Time limit exceeded
3 Incorrect 972 ms 26716 KB Output isn't correct
4 Incorrect 967 ms 22104 KB Output isn't correct
5 Execution timed out 1074 ms 39260 KB Time limit exceeded
6 Execution timed out 1030 ms 22364 KB Time limit exceeded
7 Incorrect 982 ms 33112 KB Output isn't correct
8 Incorrect 972 ms 26712 KB Output isn't correct
9 Incorrect 968 ms 26716 KB Output isn't correct
10 Execution timed out 1008 ms 22108 KB Time limit exceeded
11 Execution timed out 1041 ms 22108 KB Time limit exceeded
12 Incorrect 974 ms 22108 KB Output isn't correct
13 Execution timed out 1038 ms 24528 KB Time limit exceeded
14 Execution timed out 1046 ms 22104 KB Time limit exceeded
15 Incorrect 981 ms 22360 KB Output isn't correct
16 Incorrect 968 ms 22104 KB Output isn't correct
17 Incorrect 992 ms 26460 KB Output isn't correct
18 Incorrect 960 ms 24668 KB Output isn't correct
19 Incorrect 988 ms 24156 KB Output isn't correct
20 Incorrect 991 ms 26716 KB Output isn't correct
21 Incorrect 977 ms 22108 KB Output isn't correct
22 Incorrect 982 ms 29120 KB Output isn't correct
23 Incorrect 978 ms 26460 KB Output isn't correct
24 Execution timed out 1065 ms 22108 KB Time limit exceeded
25 Execution timed out 1008 ms 22104 KB Time limit exceeded
26 Incorrect 990 ms 22108 KB Output isn't correct
27 Execution timed out 1026 ms 28908 KB Time limit exceeded
28 Incorrect 992 ms 22104 KB Output isn't correct
29 Execution timed out 1004 ms 29020 KB Time limit exceeded
30 Execution timed out 1047 ms 26684 KB Time limit exceeded
31 Incorrect 964 ms 24152 KB Output isn't correct
32 Incorrect 994 ms 22108 KB Output isn't correct
33 Incorrect 958 ms 22104 KB Output isn't correct
34 Incorrect 991 ms 32348 KB Output isn't correct
35 Incorrect 989 ms 22104 KB Output isn't correct
36 Execution timed out 1025 ms 28368 KB Time limit exceeded
37 Execution timed out 1069 ms 38492 KB Time limit exceeded
38 Incorrect 984 ms 22052 KB Output isn't correct
39 Execution timed out 1002 ms 22108 KB Time limit exceeded
40 Incorrect 976 ms 22108 KB Output isn't correct
41 Execution timed out 1025 ms 34516 KB Time limit exceeded
42 Execution timed out 1032 ms 22108 KB Time limit exceeded