Submission #704027

#	Time	Username	Problem	Language	Result	Execution time	Memory
704027		Tigerpants	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	20 / 100	246 ms	262144 KiB

brunhilda

#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <random>
#include <string>
#include <deque>
#include <iomanip>
#include <queue>
#include <unordered_set>
#include <cmath>
#include <functional>

using namespace std;

typedef long long int ll;
typedef long double ld;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<bool> vb;
typedef vector<vll> vvll;
typedef vector<vld> vvld;
typedef vector<vvll> vvvll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef set<ll> sll;
typedef set<pll> spll;
typedef map<pll, ll> mpll_ll;
typedef map<ll, pll> mll_pll;
typedef string str;
typedef vector<str> vstr;

#define rep(x, a, b) for (ll x = a; x < b; x++)
#define rev_rep(x, a, b) for (ll x = a; x >= b; x--)
#define itr_rep(type_, x, b) for (type_::iterator x = b.begin(); x != b.end(); x++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) a.size()
#define resz(a, b) a.resize(b)
#define sort_all(a) sort(all(a))
#define pb(a) push_back(a)
#define fill_sz(a, b) fill_n(a.begin(), sz(a), b)

const ll MAXN = 10000000;
const ll MAXM = 100000;
const ll INF = 1000000000;

int dp[MAXN + 1] = {INF};

vll updates[MAXN + 1];
vll queries;

ll M, Q;
vll primes;


int target[MAXM];

bool dp_cmp(int a, int b) {
    if (dp[target[a]] == dp[target[b]]) return a < b;
    return dp[target[a]] < dp[target[b]];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    dp[0] = 0;

    cin >> M >> Q;
    resz(queries, Q);
    resz(primes, M);
    rep(i, 0, M) {
        cin >> primes[i];
    }
    ll BIGN = 0;
    rep(i, 0, Q) {
        cin >> queries[i];
        BIGN = max<ll>(BIGN, queries[i]);
    }
    rep(i, 0, M) {
        for (int j = primes[i]; j <= BIGN; j += primes[i]) {
            updates[j].push_back(i);
        }
    }

    set<int, decltype(dp_cmp)*> smallest(dp_cmp);
    rep(i, 0, M) {
        target[i] = 0;
        smallest.insert(i);
    }
    rep(i, 1, BIGN + 1) {
        for (vll::iterator upd = updates[i].begin(); upd != updates[i].end(); upd++) {
            smallest.erase(*upd);
        }
        if (smallest.empty()) dp[i] = INF;
        else dp[i] = dp[target[*smallest.begin()]] + 1;
        for (vll::iterator upd = updates[i].begin(); upd != updates[i].end(); upd++) {
            target[*upd] = i;
            smallest.insert(*upd);
        }
    }

    rep(q, 0, Q) {
        ll n = queries[q];
        if (dp[n] >= INF) {
            cout << "oo\n";
        } else {
            cout << dp[n] << "\n";
        }
    }

    cout << flush;

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60