oj.uz

Submission #738524

# Submission time Handle Problem Language Result Execution time Memory
738524 2023-05-09T03:21:31 Z GrindMachine Brunhilda’s Birthday (BOI13_brunhilda) C++17
97.7778 / 100
 1000 ms 82820 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e7 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n, q; cin >> n >> q;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];

    priority_queue<pll, vector<pll>, greater<pll>> pq;
    rep(i, n) pq.push({0, a[i]});

    vector<ll> dp(N, inf2);
    dp[0] = 0;

    rep1(i, N - 1) {
        while (!pq.empty()) {
            auto [val, p] = pq.top();
            pq.pop();

            ll curr = (i / p) * p;

            if (curr != val) {
                pq.push({curr, p});
                conts;
            }

            pq.push({val, p});
            dp[i] = dp[val] + 1;
            break;
        }
    }

    while (q--) {
        ll m; cin >> m;
        if (dp[m] < inf2) cout << dp[m] << endl;
        else cout << "oo" << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 78604 KB Output is correct
2 Correct 357 ms 78584 KB Output is correct
3 Correct 320 ms 78540 KB Output is correct
4 Correct 344 ms 78540 KB Output is correct
5 Correct 370 ms 78528 KB Output is correct
6 Correct 273 ms 78600 KB Output is correct
7 Correct 308 ms 78544 KB Output is correct
8 Correct 282 ms 78564 KB Output is correct
9 Correct 363 ms 78560 KB Output is correct
10 Correct 334 ms 78604 KB Output is correct
11 Correct 378 ms 78540 KB Output is correct
12 Correct 369 ms 78544 KB Output is correct
13 Correct 537 ms 78580 KB Output is correct
14 Correct 602 ms 78676 KB Output is correct
15 Correct 320 ms 78492 KB Output is correct
16 Correct 375 ms 78488 KB Output is correct
17 Correct 379 ms 78644 KB Output is correct
18 Correct 345 ms 78644 KB Output is correct

Subtask #2
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 600 ms 79092 KB Output is correct
2 Execution timed out 1004 ms 81592 KB Time limit exceeded
3 Correct 748 ms 80856 KB Output is correct
4 Correct 565 ms 78656 KB Output is correct
5 Correct 723 ms 80292 KB Output is correct
6 Correct 461 ms 78640 KB Output is correct
7 Correct 590 ms 79084 KB Output is correct
8 Correct 449 ms 78604 KB Output is correct
9 Correct 817 ms 80908 KB Output is correct
10 Correct 757 ms 80952 KB Output is correct
11 Correct 718 ms 79988 KB Output is correct
12 Correct 523 ms 78668 KB Output is correct
13 Correct 548 ms 78668 KB Output is correct
14 Correct 560 ms 78648 KB Output is correct
15 Correct 755 ms 80000 KB Output is correct
16 Execution timed out 1036 ms 81584 KB Time limit exceeded
17 Correct 554 ms 78740 KB Output is correct
18 Correct 776 ms 81864 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 80532 KB Output is correct
2 Correct 781 ms 80464 KB Output is correct
3 Correct 751 ms 80792 KB Output is correct
4 Correct 571 ms 79620 KB Output is correct
5 Correct 900 ms 82748 KB Output is correct
6 Correct 619 ms 79920 KB Output is correct
7 Correct 794 ms 82348 KB Output is correct
8 Correct 766 ms 80528 KB Output is correct
9 Correct 790 ms 80584 KB Output is correct
10 Correct 639 ms 78976 KB Output is correct
11 Correct 632 ms 79068 KB Output is correct
12 Correct 612 ms 79104 KB Output is correct
13 Correct 724 ms 80604 KB Output is correct
14 Correct 419 ms 79828 KB Output is correct
15 Correct 595 ms 79088 KB Output is correct
16 Correct 663 ms 79092 KB Output is correct
17 Correct 752 ms 80176 KB Output is correct
18 Correct 757 ms 80456 KB Output is correct
19 Correct 567 ms 79096 KB Output is correct
20 Correct 731 ms 80712 KB Output is correct
21 Correct 398 ms 79976 KB Output is correct
22 Correct 820 ms 82732 KB Output is correct
23 Correct 666 ms 80588 KB Output is correct
24 Correct 499 ms 79768 KB Output is correct
25 Correct 589 ms 79776 KB Output is correct
26 Correct 556 ms 79684 KB Output is correct
27 Correct 798 ms 82224 KB Output is correct
28 Correct 439 ms 79704 KB Output is correct
29 Correct 831 ms 82820 KB Output is correct
30 Correct 808 ms 81772 KB Output is correct
31 Correct 547 ms 79712 KB Output is correct
32 Correct 541 ms 79732 KB Output is correct
33 Correct 470 ms 79684 KB Output is correct
34 Correct 815 ms 82372 KB Output is correct
35 Correct 484 ms 79688 KB Output is correct
36 Correct 825 ms 82420 KB Output is correct
37 Correct 915 ms 82704 KB Output is correct
38 Correct 614 ms 79916 KB Output is correct
39 Correct 549 ms 79820 KB Output is correct
40 Correct 637 ms 79944 KB Output is correct
41 Correct 816 ms 82348 KB Output is correct
42 Correct 576 ms 79908 KB Output is correct