Submission #734613

# Submission time Handle Problem Language Result Execution time Memory
734613 2023-05-02T17:17:07 Z DAleksa Brunhilda’s Birthday (BOI13_brunhilda) C++17
97.7778 / 100
629 ms 194376 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[i] = -1;
        else dp[i] = dp[prv[i]] + 1;
    }
    while(q--) {
        int x;
        cin >> x;
        assert(x != 0);
        if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}
# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 163508 KB Output isn't correct
2 Correct 217 ms 185392 KB Output is correct
3 Correct 196 ms 181592 KB Output is correct
4 Correct 122 ms 159844 KB Output is correct
5 Correct 193 ms 167240 KB Output is correct
6 Incorrect 144 ms 163604 KB Output isn't correct
7 Correct 204 ms 181380 KB Output is correct
8 Correct 213 ms 186400 KB Output is correct
9 Correct 258 ms 189056 KB Output is correct
10 Correct 305 ms 190096 KB Output is correct
11 Correct 260 ms 184392 KB Output is correct
12 Correct 113 ms 159068 KB Output is correct
13 Correct 381 ms 193396 KB Output is correct
14 Correct 405 ms 193344 KB Output is correct
15 Correct 236 ms 184560 KB Output is correct
16 Correct 213 ms 185384 KB Output is correct
17 Correct 195 ms 167180 KB Output is correct
18 Correct 116 ms 159844 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 168 ms 163584 KB Output is correct
2 Correct 201 ms 166136 KB Output is correct
3 Correct 463 ms 194000 KB Output is correct
4 Correct 232 ms 172860 KB Output is correct
5 Correct 342 ms 188596 KB Output is correct
6 Correct 235 ms 180372 KB Output is correct
7 Correct 151 ms 163656 KB Output is correct
8 Correct 220 ms 171072 KB Output is correct
9 Correct 382 ms 190572 KB Output is correct
10 Correct 538 ms 194024 KB Output is correct
11 Correct 413 ms 193668 KB Output is correct
12 Correct 335 ms 186744 KB Output is correct
13 Correct 194 ms 166548 KB Output is correct
14 Correct 238 ms 172800 KB Output is correct
15 Correct 456 ms 192676 KB Output is correct
16 Correct 206 ms 166076 KB Output is correct
17 Correct 474 ms 192876 KB Output is correct
18 Correct 427 ms 191344 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 437 ms 193360 KB Output is correct
2 Correct 486 ms 193856 KB Output is correct
3 Correct 453 ms 194004 KB Output is correct
4 Correct 360 ms 188404 KB Output is correct
5 Correct 216 ms 166892 KB Output is correct
6 Correct 446 ms 191728 KB Output is correct
7 Correct 386 ms 185244 KB Output is correct
8 Correct 421 ms 193336 KB Output is correct
9 Correct 473 ms 193320 KB Output is correct
10 Correct 377 ms 184252 KB Output is correct
11 Correct 358 ms 180184 KB Output is correct
12 Correct 500 ms 191480 KB Output is correct
13 Correct 629 ms 192840 KB Output is correct
14 Correct 412 ms 191260 KB Output is correct
15 Correct 463 ms 193092 KB Output is correct
16 Correct 425 ms 193392 KB Output is correct
17 Correct 390 ms 189268 KB Output is correct
18 Correct 467 ms 193848 KB Output is correct
19 Correct 195 ms 173380 KB Output is correct
20 Correct 476 ms 193968 KB Output is correct
21 Correct 378 ms 192792 KB Output is correct
22 Correct 577 ms 194376 KB Output is correct
23 Correct 255 ms 168096 KB Output is correct
24 Correct 210 ms 164316 KB Output is correct
25 Correct 398 ms 187000 KB Output is correct
26 Correct 366 ms 188348 KB Output is correct
27 Correct 508 ms 194360 KB Output is correct
28 Correct 214 ms 171032 KB Output is correct
29 Correct 488 ms 191220 KB Output is correct
30 Correct 457 ms 189448 KB Output is correct
31 Correct 267 ms 172100 KB Output is correct
32 Correct 305 ms 175856 KB Output is correct
33 Correct 162 ms 161396 KB Output is correct
34 Correct 375 ms 185256 KB Output is correct
35 Correct 231 ms 171692 KB Output is correct
36 Correct 522 ms 194208 KB Output is correct
37 Correct 229 ms 166760 KB Output is correct
38 Correct 468 ms 191736 KB Output is correct
39 Correct 211 ms 166436 KB Output is correct
40 Correct 428 ms 190100 KB Output is correct
41 Correct 348 ms 188440 KB Output is correct
42 Correct 450 ms 193820 KB Output is correct