oj.uz

Submission #388565

# Submission time Handle Problem Language Result Execution time Memory
388565 2021-04-12T06:43:15 Z Aryan_Raina Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 329 ms 157424 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define ar array
 
const int INF = 1e17;
const int MOD = 1e9 + 7;

const int MXN = 1e7+9;
int largestPrime[MXN], dp[MXN];
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int m, q; cin>>m>>q;
    for (int i = 0; i < m; i++) {
        int p; cin>>p;
        for (int j = 0; j < MXN; j += p) 
            largestPrime[j] = p;
    }
    int ind = 0; // represents the first index which is last multiple of some prime
    for (int i = 1; i < MXN; i++) {
        while (ind + largestPrime[ind] <= i || dp[ind] > INF/2) 
            ind++;
        if (ind >= i) dp[i] = INF;
        else dp[i] = dp[ind] + 1;
    }   
    while (q--) {
        int x; cin>>x;
        if (dp[x] > INF/2) cout<<"oo\n";
        else cout<<dp[x]<<"\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 156744 KB Output is correct
2 Correct 115 ms 156788 KB Output is correct
3 Correct 132 ms 156856 KB Output is correct
4 Correct 88 ms 156816 KB Output is correct
5 Correct 108 ms 156788 KB Output is correct
6 Correct 121 ms 156736 KB Output is correct
7 Correct 129 ms 156792 KB Output is correct
8 Correct 138 ms 156868 KB Output is correct
9 Correct 156 ms 156844 KB Output is correct
10 Correct 154 ms 156832 KB Output is correct
11 Correct 140 ms 156760 KB Output is correct
12 Correct 87 ms 156996 KB Output is correct
13 Correct 234 ms 156768 KB Output is correct
14 Correct 240 ms 156788 KB Output is correct
15 Correct 135 ms 156788 KB Output is correct
16 Correct 130 ms 156740 KB Output is correct
17 Correct 111 ms 156788 KB Output is correct
18 Correct 92 ms 156792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 156740 KB Output is correct
2 Correct 124 ms 156844 KB Output is correct
3 Correct 296 ms 156784 KB Output is correct
4 Correct 132 ms 156784 KB Output is correct
5 Correct 205 ms 156832 KB Output is correct
6 Correct 107 ms 156740 KB Output is correct
7 Correct 106 ms 156824 KB Output is correct
8 Correct 120 ms 156764 KB Output is correct
9 Correct 234 ms 156828 KB Output is correct
10 Correct 309 ms 156844 KB Output is correct
11 Correct 278 ms 156740 KB Output is correct
12 Correct 163 ms 156748 KB Output is correct
13 Correct 98 ms 156796 KB Output is correct
14 Correct 124 ms 156792 KB Output is correct
15 Correct 233 ms 156736 KB Output is correct
16 Correct 122 ms 156920 KB Output is correct
17 Correct 234 ms 156800 KB Output is correct
18 Correct 241 ms 156868 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 156920 KB Output is correct
2 Correct 304 ms 156864 KB Output is correct
3 Correct 304 ms 157028 KB Output is correct
4 Correct 199 ms 157112 KB Output is correct
5 Correct 157 ms 156996 KB Output is correct
6 Correct 251 ms 157124 KB Output is correct
7 Correct 217 ms 156884 KB Output is correct
8 Correct 259 ms 156872 KB Output is correct
9 Correct 263 ms 156868 KB Output is correct
10 Correct 184 ms 156868 KB Output is correct
11 Correct 162 ms 156836 KB Output is correct
12 Correct 227 ms 156840 KB Output is correct
13 Correct 279 ms 157128 KB Output is correct
14 Correct 180 ms 157424 KB Output is correct
15 Correct 251 ms 156992 KB Output is correct
16 Correct 256 ms 156868 KB Output is correct
17 Correct 230 ms 156780 KB Output is correct
18 Correct 303 ms 156792 KB Output is correct
19 Correct 105 ms 156808 KB Output is correct
20 Correct 302 ms 156992 KB Output is correct
21 Correct 220 ms 157380 KB Output is correct
22 Correct 326 ms 156936 KB Output is correct
23 Correct 161 ms 157048 KB Output is correct
24 Correct 132 ms 157048 KB Output is correct
25 Correct 212 ms 157140 KB Output is correct
26 Correct 198 ms 157124 KB Output is correct
27 Correct 329 ms 156916 KB Output is correct
28 Correct 123 ms 157124 KB Output is correct
29 Correct 299 ms 157124 KB Output is correct
30 Correct 267 ms 157012 KB Output is correct
31 Correct 146 ms 156996 KB Output is correct
32 Correct 161 ms 157124 KB Output is correct
33 Correct 125 ms 157084 KB Output is correct
34 Correct 226 ms 156904 KB Output is correct
35 Correct 124 ms 157060 KB Output is correct
36 Correct 326 ms 156996 KB Output is correct
37 Correct 175 ms 157024 KB Output is correct
38 Correct 255 ms 157184 KB Output is correct
39 Correct 148 ms 157256 KB Output is correct
40 Correct 222 ms 156996 KB Output is correct
41 Correct 198 ms 156924 KB Output is correct
42 Correct 281 ms 157228 KB Output is correct