Submission #923654

# Submission time Handle Problem Language Result Execution time Memory
923654 2024-02-07T14:21:34 Z sleepntsheep Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
116 ms 262144 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;

#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], p[M];

multiset<int> ms;
basic_string<int> act[N], fus[N];

int main()
{
    memset(dp, 63, sizeof dp);
    ShinLena;

    dp[0] = 0;
    cin >> m >> q;
    for (int i = 1; i <= m; ++i)
    {
        cin >> p[i];
        act[1].push_back(1);
        act[p[i]].push_back(-1);
        for (int j = p[i]; j < N; j += p[i]) fus[j].push_back(p[i]);
    }

    for (int i = 1; i < N; ++i)
    {
        for (auto x : act[i])
        {
            if (x < 0) ms.erase(ms.find(-x - 1));
            else ms.insert(x - 1);
        }

        if (ms.size())
            dp[i] = min(dp[i], *ms.begin()  + 1);

        for (auto x : fus[i])
        {
            if (i + 1 < N)
                act[i+1].push_back(dp[i] + 1);
            if (i + x < N)
                act[x+i].push_back(-dp[i] - 1);
        }
        basic_string<int>().swap(act[i]);
        basic_string<int>().swap(fus[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;
}


# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 262144 KB Execution killed with signal 9
2 Runtime error 38 ms 262144 KB Execution killed with signal 9
3 Runtime error 39 ms 262144 KB Execution killed with signal 9
4 Runtime error 39 ms 262144 KB Execution killed with signal 9
5 Runtime error 39 ms 262144 KB Execution killed with signal 9
6 Runtime error 83 ms 262144 KB Execution killed with signal 9
7 Runtime error 44 ms 262144 KB Execution killed with signal 9
8 Runtime error 39 ms 262144 KB Execution killed with signal 9
9 Runtime error 40 ms 262144 KB Execution killed with signal 9
10 Runtime error 40 ms 262144 KB Execution killed with signal 9
11 Runtime error 88 ms 262144 KB Execution killed with signal 9
12 Runtime error 39 ms 262144 KB Execution killed with signal 9
13 Runtime error 38 ms 262144 KB Execution killed with signal 9
14 Runtime error 39 ms 262144 KB Execution killed with signal 9
15 Runtime error 38 ms 262144 KB Execution killed with signal 9
16 Runtime error 38 ms 262144 KB Execution killed with signal 9
17 Runtime error 41 ms 262144 KB Execution killed with signal 9
18 Runtime error 40 ms 262144 KB Execution killed with signal 9
# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 262144 KB Execution killed with signal 9
2 Runtime error 43 ms 262144 KB Execution killed with signal 9
3 Runtime error 40 ms 262144 KB Execution killed with signal 9
4 Runtime error 39 ms 262144 KB Execution killed with signal 9
5 Runtime error 41 ms 262144 KB Execution killed with signal 9
6 Runtime error 40 ms 262144 KB Execution killed with signal 9
7 Runtime error 40 ms 262144 KB Execution killed with signal 9
8 Runtime error 40 ms 262144 KB Execution killed with signal 9
9 Runtime error 38 ms 262144 KB Execution killed with signal 9
10 Runtime error 39 ms 262144 KB Execution killed with signal 9
11 Runtime error 44 ms 262144 KB Execution killed with signal 9
12 Runtime error 38 ms 262144 KB Execution killed with signal 9
13 Runtime error 39 ms 262144 KB Execution killed with signal 9
14 Runtime error 42 ms 262144 KB Execution killed with signal 9
15 Runtime error 39 ms 262144 KB Execution killed with signal 9
16 Runtime error 40 ms 262144 KB Execution killed with signal 9
17 Runtime error 39 ms 262144 KB Execution killed with signal 9
18 Runtime error 40 ms 262144 KB Execution killed with signal 9
# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 262144 KB Execution killed with signal 9
2 Runtime error 62 ms 262144 KB Execution killed with signal 9
3 Runtime error 40 ms 262144 KB Execution killed with signal 9
4 Runtime error 40 ms 262144 KB Execution killed with signal 9
5 Runtime error 40 ms 262144 KB Execution killed with signal 9
6 Runtime error 61 ms 262144 KB Execution killed with signal 9
7 Runtime error 39 ms 262144 KB Execution killed with signal 9
8 Runtime error 38 ms 262144 KB Execution killed with signal 9
9 Runtime error 40 ms 262144 KB Execution killed with signal 9
10 Runtime error 42 ms 262144 KB Execution killed with signal 9
11 Runtime error 40 ms 262144 KB Execution killed with signal 9
12 Runtime error 40 ms 262144 KB Execution killed with signal 9
13 Runtime error 39 ms 262144 KB Execution killed with signal 9
14 Runtime error 39 ms 262144 KB Execution killed with signal 9
15 Runtime error 38 ms 262144 KB Execution killed with signal 9
16 Runtime error 41 ms 262144 KB Execution killed with signal 9
17 Runtime error 39 ms 262144 KB Execution killed with signal 9
18 Runtime error 40 ms 262144 KB Execution killed with signal 9
19 Runtime error 40 ms 262144 KB Execution killed with signal 9
20 Runtime error 39 ms 262144 KB Execution killed with signal 9
21 Runtime error 68 ms 262144 KB Execution killed with signal 9
22 Runtime error 39 ms 262144 KB Execution killed with signal 9
23 Runtime error 39 ms 262144 KB Execution killed with signal 9
24 Runtime error 61 ms 262144 KB Execution killed with signal 9
25 Runtime error 39 ms 262144 KB Execution killed with signal 9
26 Runtime error 39 ms 262144 KB Execution killed with signal 9
27 Runtime error 38 ms 262144 KB Execution killed with signal 9
28 Runtime error 40 ms 262144 KB Execution killed with signal 9
29 Runtime error 41 ms 262144 KB Execution killed with signal 9
30 Runtime error 37 ms 262144 KB Execution killed with signal 9
31 Runtime error 39 ms 262144 KB Execution killed with signal 9
32 Runtime error 39 ms 262144 KB Execution killed with signal 9
33 Runtime error 40 ms 262144 KB Execution killed with signal 9
34 Runtime error 39 ms 262144 KB Execution killed with signal 9
35 Runtime error 116 ms 262144 KB Execution killed with signal 9
36 Runtime error 42 ms 262144 KB Execution killed with signal 9
37 Runtime error 37 ms 262144 KB Execution killed with signal 9
38 Runtime error 41 ms 262144 KB Execution killed with signal 9
39 Runtime error 39 ms 262144 KB Execution killed with signal 9
40 Runtime error 38 ms 262144 KB Execution killed with signal 9
41 Runtime error 39 ms 262144 KB Execution killed with signal 9
42 Runtime error 39 ms 262144 KB Execution killed with signal 9