Submission #923643

#	Time	Username	Problem	Language	Result	Execution time	Memory
923643		sleepntsheep	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	0 / 100	1074 ms	4748 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;

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

#if 0
#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];
        if (p[i] >= N) continue;
        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])
        {
            act[i+1].push_back(dp[i] + 1);
            act[x+i].push_back(-dp[i] - 1);
        }
    }

    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