oj.uz

Submission #704027

# Submission time Handle Problem Language Result Execution time Memory
704027 2023-03-01T11:50:11 Z Tigerpants Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 246 ms 262144 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 235240 KB Output is correct
2 Correct 121 ms 235432 KB Output is correct
3 Correct 121 ms 235340 KB Output is correct
4 Correct 120 ms 235292 KB Output is correct
5 Correct 120 ms 235084 KB Output is correct
6 Correct 127 ms 235212 KB Output is correct
7 Correct 126 ms 235336 KB Output is correct
8 Correct 125 ms 235340 KB Output is correct
9 Correct 126 ms 235084 KB Output is correct
10 Correct 121 ms 235340 KB Output is correct
11 Correct 120 ms 235336 KB Output is correct
12 Correct 122 ms 235084 KB Output is correct
13 Correct 128 ms 235596 KB Output is correct
14 Correct 131 ms 235724 KB Output is correct
15 Correct 126 ms 235304 KB Output is correct
16 Correct 121 ms 235432 KB Output is correct
17 Correct 123 ms 235412 KB Output is correct
18 Correct 122 ms 235280 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 202 ms 262144 KB Execution killed with signal 9
2 Runtime error 160 ms 262144 KB Execution killed with signal 9
3 Runtime error 133 ms 262144 KB Execution killed with signal 9
4 Runtime error 157 ms 262144 KB Execution killed with signal 9
5 Runtime error 137 ms 262144 KB Execution killed with signal 9
6 Runtime error 137 ms 262144 KB Execution killed with signal 9
7 Runtime error 204 ms 262144 KB Execution killed with signal 9
8 Runtime error 151 ms 262144 KB Execution killed with signal 9
9 Runtime error 137 ms 262144 KB Execution killed with signal 9
10 Runtime error 142 ms 262144 KB Execution killed with signal 9
11 Runtime error 129 ms 262144 KB Execution killed with signal 9
12 Runtime error 123 ms 262144 KB Execution killed with signal 9
13 Runtime error 126 ms 262144 KB Execution killed with signal 9
14 Runtime error 127 ms 262144 KB Execution killed with signal 9
15 Runtime error 141 ms 262144 KB Execution killed with signal 9
16 Runtime error 154 ms 262144 KB Execution killed with signal 9
17 Runtime error 137 ms 262144 KB Execution killed with signal 9
18 Runtime error 132 ms 262144 KB Execution killed with signal 9

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 137 ms 262144 KB Execution killed with signal 9
2 Runtime error 133 ms 262144 KB Execution killed with signal 9
3 Runtime error 140 ms 262144 KB Execution killed with signal 9
4 Runtime error 142 ms 262144 KB Execution killed with signal 9
5 Runtime error 242 ms 262144 KB Execution killed with signal 9
6 Runtime error 137 ms 262144 KB Execution killed with signal 9
7 Runtime error 149 ms 262144 KB Execution killed with signal 9
8 Runtime error 150 ms 262144 KB Execution killed with signal 9
9 Runtime error 135 ms 262144 KB Execution killed with signal 9
10 Runtime error 137 ms 262144 KB Execution killed with signal 9
11 Runtime error 128 ms 262144 KB Execution killed with signal 9
12 Runtime error 131 ms 262144 KB Execution killed with signal 9
13 Runtime error 138 ms 262144 KB Execution killed with signal 9
14 Runtime error 136 ms 262144 KB Execution killed with signal 9
15 Runtime error 136 ms 262144 KB Execution killed with signal 9
16 Runtime error 129 ms 262144 KB Execution killed with signal 9
17 Runtime error 133 ms 262144 KB Execution killed with signal 9
18 Runtime error 137 ms 262144 KB Execution killed with signal 9
19 Runtime error 131 ms 262144 KB Execution killed with signal 9
20 Runtime error 135 ms 262144 KB Execution killed with signal 9
21 Runtime error 141 ms 262144 KB Execution killed with signal 9
22 Runtime error 141 ms 262144 KB Execution killed with signal 9
23 Runtime error 246 ms 262144 KB Execution killed with signal 9
24 Runtime error 144 ms 262144 KB Execution killed with signal 9
25 Runtime error 135 ms 262144 KB Execution killed with signal 9
26 Runtime error 136 ms 262144 KB Execution killed with signal 9
27 Runtime error 138 ms 262144 KB Execution killed with signal 9
28 Runtime error 136 ms 262144 KB Execution killed with signal 9
29 Runtime error 146 ms 262144 KB Execution killed with signal 9
30 Runtime error 148 ms 262144 KB Execution killed with signal 9
31 Runtime error 142 ms 262144 KB Execution killed with signal 9
32 Runtime error 155 ms 262144 KB Execution killed with signal 9
33 Runtime error 167 ms 262144 KB Execution killed with signal 9
34 Runtime error 166 ms 262144 KB Execution killed with signal 9
35 Runtime error 132 ms 262144 KB Execution killed with signal 9
36 Runtime error 142 ms 262144 KB Execution killed with signal 9
37 Runtime error 233 ms 262144 KB Execution killed with signal 9
38 Runtime error 137 ms 262144 KB Execution killed with signal 9
39 Runtime error 148 ms 262144 KB Execution killed with signal 9
40 Runtime error 138 ms 262144 KB Execution killed with signal 9
41 Runtime error 145 ms 262144 KB Execution killed with signal 9
42 Runtime error 136 ms 262144 KB Execution killed with signal 9