oj.uz

Submission #738526

# Submission time Handle Problem Language Result Execution time Memory
738526 2023-05-09T03:28:30 Z GrindMachine Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 972 ms 80060 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

/*

ig i read the edi for this problem a long time ago (dont remember the approach in the edi tho)

greedy strategy
=> in each op, try to reduce the number as much as possible
because the #of ops is a montonic sequence

if we need k ops to make n1 = 0, then we would need <= k ops to make n2 = 0, n2 < n1
because we can apply the same k ops we applied to n1 to n2 and n2 would also become 0

i remember seeing this idea somewhere => maybe in the edi of this problem/some other problem

*/

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)
{
    int n, q; cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

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

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

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

            int curr = (i / p) * p;

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

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

    while (q--) {
        int m; cin >> m;
        if (dp[m] < inf1) 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 325 ms 78592 KB Output is correct
2 Correct 324 ms 78544 KB Output is correct
3 Correct 352 ms 78548 KB Output is correct
4 Correct 364 ms 78596 KB Output is correct
5 Correct 346 ms 78468 KB Output is correct
6 Correct 317 ms 78592 KB Output is correct
7 Correct 336 ms 78524 KB Output is correct
8 Correct 335 ms 78684 KB Output is correct
9 Correct 381 ms 78552 KB Output is correct
10 Correct 356 ms 78588 KB Output is correct
11 Correct 349 ms 78596 KB Output is correct
12 Correct 341 ms 78548 KB Output is correct
13 Correct 514 ms 78580 KB Output is correct
14 Correct 540 ms 78616 KB Output is correct
15 Correct 313 ms 78480 KB Output is correct
16 Correct 367 ms 78548 KB Output is correct
17 Correct 345 ms 78592 KB Output is correct
18 Correct 329 ms 78596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 78864 KB Output is correct
2 Correct 972 ms 79800 KB Output is correct
3 Correct 703 ms 79552 KB Output is correct
4 Correct 569 ms 78540 KB Output is correct
5 Correct 693 ms 79336 KB Output is correct
6 Correct 443 ms 78536 KB Output is correct
7 Correct 575 ms 78864 KB Output is correct
8 Correct 433 ms 78548 KB Output is correct
9 Correct 798 ms 79624 KB Output is correct
10 Correct 742 ms 79448 KB Output is correct
11 Correct 702 ms 79208 KB Output is correct
12 Correct 559 ms 78540 KB Output is correct
13 Correct 511 ms 78572 KB Output is correct
14 Correct 535 ms 78620 KB Output is correct
15 Correct 737 ms 79220 KB Output is correct
16 Correct 970 ms 79820 KB Output is correct
17 Correct 522 ms 78676 KB Output is correct
18 Correct 727 ms 79904 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 709 ms 79312 KB Output is correct
2 Correct 725 ms 79348 KB Output is correct
3 Correct 704 ms 79440 KB Output is correct
4 Correct 561 ms 78920 KB Output is correct
5 Correct 878 ms 80024 KB Output is correct
6 Correct 607 ms 79088 KB Output is correct
7 Correct 763 ms 79908 KB Output is correct
8 Correct 772 ms 79312 KB Output is correct
9 Correct 704 ms 79312 KB Output is correct
10 Correct 590 ms 78676 KB Output is correct
11 Correct 594 ms 78716 KB Output is correct
12 Correct 630 ms 78728 KB Output is correct
13 Correct 675 ms 79436 KB Output is correct
14 Correct 436 ms 79104 KB Output is correct
15 Correct 573 ms 78724 KB Output is correct
16 Correct 615 ms 78744 KB Output is correct
17 Correct 781 ms 79256 KB Output is correct
18 Correct 806 ms 79348 KB Output is correct
19 Correct 566 ms 78720 KB Output is correct
20 Correct 725 ms 79420 KB Output is correct
21 Correct 386 ms 79120 KB Output is correct
22 Correct 817 ms 80032 KB Output is correct
23 Correct 652 ms 79288 KB Output is correct
24 Correct 521 ms 78880 KB Output is correct
25 Correct 590 ms 78924 KB Output is correct
26 Correct 590 ms 78928 KB Output is correct
27 Correct 819 ms 79944 KB Output is correct
28 Correct 473 ms 78868 KB Output is correct
29 Correct 798 ms 80036 KB Output is correct
30 Correct 803 ms 79676 KB Output is correct
31 Correct 538 ms 78840 KB Output is correct
32 Correct 531 ms 78928 KB Output is correct
33 Correct 460 ms 78760 KB Output is correct
34 Correct 760 ms 80016 KB Output is correct
35 Correct 484 ms 78924 KB Output is correct
36 Correct 793 ms 79908 KB Output is correct
37 Correct 868 ms 80060 KB Output is correct
38 Correct 621 ms 79008 KB Output is correct
39 Correct 528 ms 78916 KB Output is correct
40 Correct 656 ms 79088 KB Output is correct
41 Correct 769 ms 79904 KB Output is correct
42 Correct 563 ms 79052 KB Output is correct