oj.uz

Submission #757439

# Submission time Handle Problem Language Result Execution time Memory
757439 2023-06-13T07:43:43 Z dxz05 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 341 ms 79844 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e7 + 2;

int dp[N];
int max_p[N];

void solve(){
    int m, q;
    cin >> m >> q;

    vector<int> primes(m);
    for (int i = 0; i < m; i++) cin >> primes[i];

    for (int p : primes){
        for (int i = 0; i < N; i += p) max_p[i] = p;
    }

    fill(dp + 1, dp + N, 1e9);

    int l = 0, r = 0;
    int val = 0;

    while (r < N){
        if (l > r) break;

        int nxt_r = r;
        for (int i = l; i <= r; i++){
            dp[i] = val;

            int p = max_p[i];
            if (p == 0) continue;
            nxt_r = max(nxt_r, i + p - 1);
        }

        nxt_r = min(nxt_r, N - 1);
        l = r + 1;
        r = nxt_r;
        val++;
    }

    while (q--){
        int i;
        cin >> i;
        if (dp[i] != 1e9){
            cout << dp[i] << "\n";
        } else {
            cout << "oo\n";
        }
    }

}

int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int test_cases = 1;
//    cin >> test_cases;

    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }

#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:71:13: warning: unused variable 'startTime' [-Wunused-variable]
   71 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 78564 KB Output is correct
2 Correct 66 ms 78500 KB Output is correct
3 Correct 44 ms 78540 KB Output is correct
4 Correct 60 ms 78584 KB Output is correct
5 Correct 79 ms 78484 KB Output is correct
6 Correct 38 ms 78472 KB Output is correct
7 Correct 45 ms 78580 KB Output is correct
8 Correct 49 ms 78584 KB Output is correct
9 Correct 86 ms 78552 KB Output is correct
10 Correct 96 ms 78488 KB Output is correct
11 Correct 103 ms 78616 KB Output is correct
12 Correct 47 ms 78580 KB Output is correct
13 Correct 140 ms 78512 KB Output is correct
14 Correct 153 ms 78604 KB Output is correct
15 Correct 82 ms 78584 KB Output is correct
16 Correct 68 ms 78540 KB Output is correct
17 Correct 97 ms 78508 KB Output is correct
18 Correct 68 ms 78632 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 78528 KB Output is correct
2 Correct 81 ms 78876 KB Output is correct
3 Correct 179 ms 78780 KB Output is correct
4 Correct 120 ms 78504 KB Output is correct
5 Correct 128 ms 78720 KB Output is correct
6 Correct 64 ms 78556 KB Output is correct
7 Correct 75 ms 78532 KB Output is correct
8 Correct 100 ms 78540 KB Output is correct
9 Correct 142 ms 78916 KB Output is correct
10 Correct 186 ms 78796 KB Output is correct
11 Correct 182 ms 78736 KB Output is correct
12 Correct 108 ms 78592 KB Output is correct
13 Correct 62 ms 78636 KB Output is correct
14 Correct 103 ms 78512 KB Output is correct
15 Correct 139 ms 78664 KB Output is correct
16 Correct 80 ms 78856 KB Output is correct
17 Correct 152 ms 78516 KB Output is correct
18 Correct 149 ms 78896 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 78960 KB Output is correct
2 Correct 236 ms 78900 KB Output is correct
3 Correct 250 ms 79096 KB Output is correct
4 Correct 230 ms 79392 KB Output is correct
5 Correct 227 ms 79820 KB Output is correct
6 Correct 272 ms 79400 KB Output is correct
7 Correct 232 ms 79316 KB Output is correct
8 Correct 222 ms 78948 KB Output is correct
9 Correct 219 ms 78924 KB Output is correct
10 Correct 170 ms 78644 KB Output is correct
11 Correct 158 ms 78780 KB Output is correct
12 Correct 175 ms 78848 KB Output is correct
13 Correct 291 ms 79424 KB Output is correct
14 Correct 248 ms 79760 KB Output is correct
15 Correct 195 ms 78672 KB Output is correct
16 Correct 211 ms 78676 KB Output is correct
17 Correct 196 ms 78692 KB Output is correct
18 Correct 221 ms 78876 KB Output is correct
19 Correct 98 ms 78728 KB Output is correct
20 Correct 292 ms 79220 KB Output is correct
21 Correct 266 ms 79820 KB Output is correct
22 Correct 341 ms 79788 KB Output is correct
23 Correct 255 ms 79660 KB Output is correct
24 Correct 212 ms 79560 KB Output is correct
25 Correct 261 ms 79532 KB Output is correct
26 Correct 259 ms 79404 KB Output is correct
27 Correct 277 ms 79280 KB Output is correct
28 Correct 202 ms 79552 KB Output is correct
29 Correct 315 ms 79792 KB Output is correct
30 Correct 330 ms 79680 KB Output is correct
31 Correct 210 ms 79308 KB Output is correct
32 Correct 236 ms 79500 KB Output is correct
33 Correct 185 ms 79456 KB Output is correct
34 Correct 208 ms 79372 KB Output is correct
35 Correct 232 ms 79568 KB Output is correct
36 Correct 300 ms 79624 KB Output is correct
37 Correct 235 ms 79844 KB Output is correct
38 Correct 289 ms 79468 KB Output is correct
39 Correct 220 ms 79516 KB Output is correct
40 Correct 248 ms 79392 KB Output is correct
41 Correct 191 ms 79140 KB Output is correct
42 Correct 284 ms 79624 KB Output is correct