oj.uz

Submission #734623

# Submission time Handle Problem Language Result Execution time Memory
734623 2023-05-02T17:27:40 Z DAleksa Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 508 ms 194540 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e7 + 10;
int n, q;
vector<int> p;
vector<int> v;
int cnt[N];
int prime[N];
int prv[N];
int dp[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    p.resize(n);
    for(int i = 0; i < n; i++) cin >> p[i];
    for(int i = p.size() - 1; i >= 0; i--) {
        for(int j = p[i]; j < N; j += p[i]) {
            if(prime[j] == 0) {
                cnt[j]++;
                prime[j] = p[i];
            }
        }
    }
    cnt[0]++;
    prime[0] = p.back();
    for(int i = 0; i < N; i++) for(int j = 0; j < cnt[i]; j++) v.push_back(i);
    int j = 0;
    for(int i = 1; i < N; i++) {
        while(v[j] + prime[v[j]] <= i) j++;
        prv[i] = v[j];
    }
    for(int i = 1; i < N; i++) {
        if(prv[i] == i || dp[prv[i]] == -1) dp[i] = -1;
        else dp[i] = dp[prv[i]] + 1;
    }
    while(q--) {
        int x;
        cin >> x;
        if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 163552 KB Output is correct
2 Correct 212 ms 185432 KB Output is correct
3 Correct 193 ms 181364 KB Output is correct
4 Correct 115 ms 159908 KB Output is correct
5 Correct 186 ms 167196 KB Output is correct
6 Correct 162 ms 163648 KB Output is correct
7 Correct 194 ms 181400 KB Output is correct
8 Correct 218 ms 186336 KB Output is correct
9 Correct 275 ms 189148 KB Output is correct
10 Correct 333 ms 190048 KB Output is correct
11 Correct 277 ms 184448 KB Output is correct
12 Correct 115 ms 159020 KB Output is correct
13 Correct 400 ms 193380 KB Output is correct
14 Correct 405 ms 193408 KB Output is correct
15 Correct 241 ms 184584 KB Output is correct
16 Correct 236 ms 185372 KB Output is correct
17 Correct 216 ms 167316 KB Output is correct
18 Correct 119 ms 159908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 163564 KB Output is correct
2 Correct 184 ms 166028 KB Output is correct
3 Correct 405 ms 194096 KB Output is correct
4 Correct 225 ms 172848 KB Output is correct
5 Correct 348 ms 188628 KB Output is correct
6 Correct 206 ms 180440 KB Output is correct
7 Correct 153 ms 163620 KB Output is correct
8 Correct 227 ms 171060 KB Output is correct
9 Correct 393 ms 190572 KB Output is correct
10 Correct 444 ms 194100 KB Output is correct
11 Correct 432 ms 193644 KB Output is correct
12 Correct 303 ms 186876 KB Output is correct
13 Correct 150 ms 166580 KB Output is correct
14 Correct 251 ms 172840 KB Output is correct
15 Correct 382 ms 192668 KB Output is correct
16 Correct 191 ms 166044 KB Output is correct
17 Correct 452 ms 192980 KB Output is correct
18 Correct 395 ms 191432 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 193376 KB Output is correct
2 Correct 442 ms 193824 KB Output is correct
3 Correct 508 ms 194196 KB Output is correct
4 Correct 343 ms 188292 KB Output is correct
5 Correct 208 ms 166812 KB Output is correct
6 Correct 418 ms 191828 KB Output is correct
7 Correct 345 ms 185228 KB Output is correct
8 Correct 466 ms 193328 KB Output is correct
9 Correct 419 ms 193340 KB Output is correct
10 Correct 337 ms 184188 KB Output is correct
11 Correct 310 ms 180120 KB Output is correct
12 Correct 380 ms 191492 KB Output is correct
13 Correct 442 ms 192816 KB Output is correct
14 Correct 347 ms 191380 KB Output is correct
15 Correct 402 ms 193116 KB Output is correct
16 Correct 447 ms 193404 KB Output is correct
17 Correct 364 ms 189256 KB Output is correct
18 Correct 456 ms 193888 KB Output is correct
19 Correct 199 ms 173432 KB Output is correct
20 Correct 492 ms 194056 KB Output is correct
21 Correct 396 ms 192740 KB Output is correct
22 Correct 490 ms 194340 KB Output is correct
23 Correct 242 ms 168140 KB Output is correct
24 Correct 193 ms 164372 KB Output is correct
25 Correct 347 ms 186984 KB Output is correct
26 Correct 357 ms 188360 KB Output is correct
27 Correct 483 ms 194540 KB Output is correct
28 Correct 210 ms 171084 KB Output is correct
29 Correct 440 ms 191196 KB Output is correct
30 Correct 415 ms 189500 KB Output is correct
31 Correct 232 ms 172060 KB Output is correct
32 Correct 277 ms 175908 KB Output is correct
33 Correct 162 ms 161320 KB Output is correct
34 Correct 334 ms 185180 KB Output is correct
35 Correct 220 ms 171788 KB Output is correct
36 Correct 449 ms 194252 KB Output is correct
37 Correct 197 ms 166868 KB Output is correct
38 Correct 408 ms 191884 KB Output is correct
39 Correct 202 ms 166432 KB Output is correct
40 Correct 380 ms 190160 KB Output is correct
41 Correct 327 ms 188472 KB Output is correct
42 Correct 434 ms 193824 KB Output is correct