oj.uz

Submission #738525

# Submission time Handle Problem Language Result Execution time Memory
738525 2023-05-09T03:23:59 Z GrindMachine Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 993 ms 80036 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)
{
    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 324 ms 78596 KB Output is correct
2 Correct 338 ms 78500 KB Output is correct
3 Correct 324 ms 78564 KB Output is correct
4 Correct 345 ms 78560 KB Output is correct
5 Correct 331 ms 78536 KB Output is correct
6 Correct 339 ms 78588 KB Output is correct
7 Correct 325 ms 78540 KB Output is correct
8 Correct 336 ms 78540 KB Output is correct
9 Correct 363 ms 78540 KB Output is correct
10 Correct 351 ms 78540 KB Output is correct
11 Correct 338 ms 78488 KB Output is correct
12 Correct 333 ms 78548 KB Output is correct
13 Correct 507 ms 78604 KB Output is correct
14 Correct 548 ms 78612 KB Output is correct
15 Correct 320 ms 78472 KB Output is correct
16 Correct 357 ms 78484 KB Output is correct
17 Correct 354 ms 78596 KB Output is correct
18 Correct 332 ms 78604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 78860 KB Output is correct
2 Correct 991 ms 79808 KB Output is correct
3 Correct 749 ms 79584 KB Output is correct
4 Correct 532 ms 78608 KB Output is correct
5 Correct 683 ms 79332 KB Output is correct
6 Correct 474 ms 78560 KB Output is correct
7 Correct 573 ms 78868 KB Output is correct
8 Correct 437 ms 78512 KB Output is correct
9 Correct 786 ms 79568 KB Output is correct
10 Correct 714 ms 79548 KB Output is correct
11 Correct 757 ms 79196 KB Output is correct
12 Correct 514 ms 78588 KB Output is correct
13 Correct 533 ms 78544 KB Output is correct
14 Correct 528 ms 78644 KB Output is correct
15 Correct 776 ms 79212 KB Output is correct
16 Correct 993 ms 79808 KB Output is correct
17 Correct 558 ms 78664 KB Output is correct
18 Correct 751 ms 79940 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 79316 KB Output is correct
2 Correct 739 ms 79344 KB Output is correct
3 Correct 716 ms 79444 KB Output is correct
4 Correct 578 ms 78944 KB Output is correct
5 Correct 871 ms 80020 KB Output is correct
6 Correct 597 ms 79008 KB Output is correct
7 Correct 761 ms 79908 KB Output is correct
8 Correct 712 ms 79316 KB Output is correct
9 Correct 704 ms 79316 KB Output is correct
10 Correct 591 ms 78732 KB Output is correct
11 Correct 581 ms 78716 KB Output is correct
12 Correct 600 ms 78732 KB Output is correct
13 Correct 673 ms 79332 KB Output is correct
14 Correct 406 ms 79180 KB Output is correct
15 Correct 623 ms 78724 KB Output is correct
16 Correct 613 ms 78808 KB Output is correct
17 Correct 694 ms 79252 KB Output is correct
18 Correct 744 ms 79344 KB Output is correct
19 Correct 563 ms 78716 KB Output is correct
20 Correct 737 ms 79444 KB Output is correct
21 Correct 391 ms 79108 KB Output is correct
22 Correct 796 ms 80036 KB Output is correct
23 Correct 668 ms 79200 KB Output is correct
24 Correct 510 ms 78888 KB Output is correct
25 Correct 590 ms 78916 KB Output is correct
26 Correct 549 ms 78932 KB Output is correct
27 Correct 780 ms 79908 KB Output is correct
28 Correct 457 ms 78868 KB Output is correct
29 Correct 849 ms 80032 KB Output is correct
30 Correct 810 ms 79676 KB Output is correct
31 Correct 555 ms 78840 KB Output is correct
32 Correct 567 ms 78916 KB Output is correct
33 Correct 471 ms 78756 KB Output is correct
34 Correct 807 ms 80032 KB Output is correct
35 Correct 467 ms 78896 KB Output is correct
36 Correct 818 ms 79916 KB Output is correct
37 Correct 875 ms 80012 KB Output is correct
38 Correct 654 ms 79012 KB Output is correct
39 Correct 555 ms 78916 KB Output is correct
40 Correct 641 ms 78968 KB Output is correct
41 Correct 793 ms 79908 KB Output is correct
42 Correct 583 ms 79048 KB Output is correct