oj.uz

Submission #757444

# Submission time Handle Problem Language Result Execution time Memory
757444 2023-06-13T07:46:46 Z dxz05 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 342 ms 79144 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;

    while (m--){
        int p;
        cin >> p;
        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:70:13: warning: unused variable 'startTime' [-Wunused-variable]
   70 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78540 KB Output is correct
2 Correct 68 ms 78484 KB Output is correct
3 Correct 47 ms 78492 KB Output is correct
4 Correct 64 ms 78540 KB Output is correct
5 Correct 75 ms 78488 KB Output is correct
6 Correct 46 ms 78516 KB Output is correct
7 Correct 50 ms 78508 KB Output is correct
8 Correct 50 ms 78500 KB Output is correct
9 Correct 86 ms 78488 KB Output is correct
10 Correct 95 ms 78508 KB Output is correct
11 Correct 115 ms 78536 KB Output is correct
12 Correct 49 ms 78552 KB Output is correct
13 Correct 142 ms 78500 KB Output is correct
14 Correct 148 ms 78496 KB Output is correct
15 Correct 84 ms 78540 KB Output is correct
16 Correct 67 ms 78488 KB Output is correct
17 Correct 90 ms 78568 KB Output is correct
18 Correct 61 ms 78668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 78488 KB Output is correct
2 Correct 95 ms 78504 KB Output is correct
3 Correct 179 ms 78500 KB Output is correct
4 Correct 98 ms 78548 KB Output is correct
5 Correct 137 ms 78584 KB Output is correct
6 Correct 69 ms 78540 KB Output is correct
7 Correct 68 ms 78592 KB Output is correct
8 Correct 103 ms 78588 KB Output is correct
9 Correct 167 ms 78504 KB Output is correct
10 Correct 175 ms 78684 KB Output is correct
11 Correct 172 ms 78488 KB Output is correct
12 Correct 108 ms 78616 KB Output is correct
13 Correct 63 ms 78588 KB Output is correct
14 Correct 109 ms 78540 KB Output is correct
15 Correct 145 ms 78492 KB Output is correct
16 Correct 87 ms 78488 KB Output is correct
17 Correct 161 ms 78528 KB Output is correct
18 Correct 159 ms 78492 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 78632 KB Output is correct
2 Correct 210 ms 78620 KB Output is correct
3 Correct 255 ms 78676 KB Output is correct
4 Correct 223 ms 78816 KB Output is correct
5 Correct 230 ms 78832 KB Output is correct
6 Correct 268 ms 78748 KB Output is correct
7 Correct 212 ms 78844 KB Output is correct
8 Correct 203 ms 78668 KB Output is correct
9 Correct 201 ms 78596 KB Output is correct
10 Correct 144 ms 78624 KB Output is correct
11 Correct 154 ms 78636 KB Output is correct
12 Correct 172 ms 78628 KB Output is correct
13 Correct 279 ms 78872 KB Output is correct
14 Correct 244 ms 79144 KB Output is correct
15 Correct 171 ms 78624 KB Output is correct
16 Correct 204 ms 78668 KB Output is correct
17 Correct 163 ms 78500 KB Output is correct
18 Correct 211 ms 78668 KB Output is correct
19 Correct 88 ms 78540 KB Output is correct
20 Correct 259 ms 78860 KB Output is correct
21 Correct 245 ms 79124 KB Output is correct
22 Correct 342 ms 78760 KB Output is correct
23 Correct 226 ms 78808 KB Output is correct
24 Correct 216 ms 78796 KB Output is correct
25 Correct 258 ms 78796 KB Output is correct
26 Correct 232 ms 78752 KB Output is correct
27 Correct 266 ms 78580 KB Output is correct
28 Correct 214 ms 78976 KB Output is correct
29 Correct 332 ms 78876 KB Output is correct
30 Correct 294 ms 78756 KB Output is correct
31 Correct 215 ms 78796 KB Output is correct
32 Correct 228 ms 78848 KB Output is correct
33 Correct 183 ms 78772 KB Output is correct
34 Correct 235 ms 78616 KB Output is correct
35 Correct 216 ms 78988 KB Output is correct
36 Correct 336 ms 78744 KB Output is correct
37 Correct 231 ms 78672 KB Output is correct
38 Correct 260 ms 78752 KB Output is correct
39 Correct 208 ms 78788 KB Output is correct
40 Correct 250 ms 78760 KB Output is correct
41 Correct 199 ms 78632 KB Output is correct
42 Correct 280 ms 79012 KB Output is correct