oj.uz

Submission #923710

# Submission time Handle Problem Language Result Execution time Memory
923710 2024-02-07T15:33:22 Z sleepntsheep Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 236 ms 80328 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39516 KB Output is correct
2 Correct 58 ms 78512 KB Output is correct
3 Correct 33 ms 41804 KB Output is correct
4 Correct 43 ms 78784 KB Output is correct
5 Correct 47 ms 78536 KB Output is correct
6 Correct 29 ms 39512 KB Output is correct
7 Correct 32 ms 41824 KB Output is correct
8 Correct 37 ms 43792 KB Output is correct
9 Correct 62 ms 78676 KB Output is correct
10 Correct 73 ms 78680 KB Output is correct
11 Correct 69 ms 78488 KB Output is correct
12 Correct 40 ms 78684 KB Output is correct
13 Correct 146 ms 78516 KB Output is correct
14 Correct 191 ms 78680 KB Output is correct
15 Correct 70 ms 78672 KB Output is correct
16 Correct 56 ms 78628 KB Output is correct
17 Correct 60 ms 78736 KB Output is correct
18 Correct 41 ms 78672 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 78672 KB Output is correct
2 Correct 64 ms 79184 KB Output is correct
3 Correct 189 ms 78976 KB Output is correct
4 Correct 69 ms 78504 KB Output is correct
5 Correct 120 ms 78988 KB Output is correct
6 Correct 55 ms 78672 KB Output is correct
7 Correct 62 ms 78672 KB Output is correct
8 Correct 67 ms 78700 KB Output is correct
9 Correct 154 ms 79020 KB Output is correct
10 Correct 203 ms 79016 KB Output is correct
11 Correct 187 ms 78728 KB Output is correct
12 Correct 90 ms 78516 KB Output is correct
13 Correct 43 ms 78500 KB Output is correct
14 Correct 69 ms 78676 KB Output is correct
15 Correct 142 ms 78760 KB Output is correct
16 Correct 69 ms 79288 KB Output is correct
17 Correct 150 ms 78512 KB Output is correct
18 Correct 157 ms 79552 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 79272 KB Output is correct
2 Correct 200 ms 79272 KB Output is correct
3 Correct 198 ms 79528 KB Output is correct
4 Correct 116 ms 79440 KB Output is correct
5 Correct 89 ms 80328 KB Output is correct
6 Correct 159 ms 79536 KB Output is correct
7 Correct 168 ms 79784 KB Output is correct
8 Correct 156 ms 79276 KB Output is correct
9 Correct 160 ms 79280 KB Output is correct
10 Correct 119 ms 78676 KB Output is correct
11 Correct 128 ms 78780 KB Output is correct
12 Correct 146 ms 78928 KB Output is correct
13 Correct 221 ms 79856 KB Output is correct
14 Correct 96 ms 79996 KB Output is correct
15 Correct 150 ms 78936 KB Output is correct
16 Correct 236 ms 78672 KB Output is correct
17 Correct 156 ms 78688 KB Output is correct
18 Correct 199 ms 78672 KB Output is correct
19 Correct 54 ms 78680 KB Output is correct
20 Correct 232 ms 79000 KB Output is correct
21 Correct 117 ms 79952 KB Output is correct
22 Correct 208 ms 79456 KB Output is correct
23 Correct 94 ms 79512 KB Output is correct
24 Correct 80 ms 79632 KB Output is correct
25 Correct 188 ms 79440 KB Output is correct
26 Correct 131 ms 79516 KB Output is correct
27 Correct 225 ms 79256 KB Output is correct
28 Correct 72 ms 79736 KB Output is correct
29 Correct 201 ms 79460 KB Output is correct
30 Correct 227 ms 79516 KB Output is correct
31 Correct 80 ms 79384 KB Output is correct
32 Correct 95 ms 79496 KB Output is correct
33 Correct 60 ms 79448 KB Output is correct
34 Correct 147 ms 79820 KB Output is correct
35 Correct 78 ms 79804 KB Output is correct
36 Correct 236 ms 80268 KB Output is correct
37 Correct 93 ms 80232 KB Output is correct
38 Correct 174 ms 79548 KB Output is correct
39 Correct 79 ms 79696 KB Output is correct
40 Correct 146 ms 79712 KB Output is correct
41 Correct 139 ms 79800 KB Output is correct
42 Correct 167 ms 79996 KB Output is correct