oj.uz

Submission #734616

# Submission time Handle Problem Language Result Execution time Memory
734616 2023-05-02T17:18:18 Z DAleksa Brunhilda’s Birthday (BOI13_brunhilda) C++17
36.0317 / 100
 508 ms 194428 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 + 1) 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;
        if(x < p.back()) cout << "1\n";
        else if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 163544 KB Output isn't correct
2 Incorrect 218 ms 185308 KB Output isn't correct
3 Incorrect 213 ms 181380 KB Output isn't correct
4 Incorrect 123 ms 159808 KB Output isn't correct
5 Incorrect 206 ms 167276 KB Output isn't correct
6 Incorrect 155 ms 163532 KB Output isn't correct
7 Incorrect 198 ms 181472 KB Output isn't correct
8 Incorrect 284 ms 186404 KB Output isn't correct
9 Incorrect 272 ms 189008 KB Output isn't correct
10 Incorrect 301 ms 190072 KB Output isn't correct
11 Incorrect 283 ms 184380 KB Output isn't correct
12 Correct 113 ms 159088 KB Output is correct
13 Correct 440 ms 193396 KB Output is correct
14 Correct 469 ms 193356 KB Output is correct
15 Incorrect 284 ms 184516 KB Output isn't correct
16 Incorrect 232 ms 185380 KB Output isn't correct
17 Incorrect 209 ms 167224 KB Output isn't correct
18 Incorrect 143 ms 159796 KB Output isn't correct

Subtask #2
15.5555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 163584 KB Output is correct
2 Correct 189 ms 166084 KB Output is correct
3 Correct 491 ms 194064 KB Output is correct
4 Incorrect 254 ms 172852 KB Output isn't correct
5 Correct 415 ms 188504 KB Output is correct
6 Correct 210 ms 180396 KB Output is correct
7 Correct 167 ms 163832 KB Output is correct
8 Correct 223 ms 171056 KB Output is correct
9 Correct 377 ms 190596 KB Output is correct
10 Correct 420 ms 193972 KB Output is correct
11 Correct 433 ms 193712 KB Output is correct
12 Incorrect 298 ms 186796 KB Output isn't correct
13 Incorrect 168 ms 166504 KB Output isn't correct
14 Incorrect 230 ms 172748 KB Output isn't correct
15 Correct 389 ms 192788 KB Output is correct
16 Correct 186 ms 166044 KB Output is correct
17 Correct 414 ms 192960 KB Output is correct
18 Correct 404 ms 191404 KB Output is correct

Subtask #3
17.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 384 ms 193352 KB Output isn't correct
2 Incorrect 421 ms 193808 KB Output isn't correct
3 Correct 441 ms 194324 KB Output is correct
4 Incorrect 313 ms 188276 KB Output isn't correct
5 Correct 205 ms 166856 KB Output is correct
6 Incorrect 398 ms 191788 KB Output isn't correct
7 Correct 346 ms 185212 KB Output is correct
8 Incorrect 382 ms 193380 KB Output isn't correct
9 Incorrect 375 ms 193404 KB Output isn't correct
10 Incorrect 349 ms 184304 KB Output isn't correct
11 Incorrect 301 ms 180212 KB Output isn't correct
12 Incorrect 368 ms 191408 KB Output isn't correct
13 Correct 409 ms 192896 KB Output is correct
14 Incorrect 326 ms 191352 KB Output isn't correct
15 Incorrect 398 ms 193092 KB Output isn't correct
16 Incorrect 419 ms 193388 KB Output isn't correct
17 Incorrect 397 ms 189264 KB Output isn't correct
18 Incorrect 454 ms 193888 KB Output isn't correct
19 Incorrect 170 ms 173632 KB Output isn't correct
20 Correct 465 ms 194088 KB Output is correct
21 Incorrect 344 ms 192772 KB Output isn't correct
22 Correct 475 ms 194408 KB Output is correct
23 Incorrect 227 ms 168100 KB Output isn't correct
24 Incorrect 194 ms 164320 KB Output isn't correct
25 Incorrect 368 ms 187016 KB Output isn't correct
26 Incorrect 413 ms 188352 KB Output isn't correct
27 Correct 505 ms 194428 KB Output is correct
28 Incorrect 224 ms 171032 KB Output isn't correct
29 Correct 460 ms 191136 KB Output is correct
30 Incorrect 450 ms 189492 KB Output isn't correct
31 Incorrect 251 ms 172068 KB Output isn't correct
32 Incorrect 311 ms 175856 KB Output isn't correct
33 Incorrect 169 ms 161324 KB Output isn't correct
34 Correct 393 ms 185196 KB Output is correct
35 Incorrect 233 ms 171784 KB Output isn't correct
36 Correct 493 ms 194252 KB Output is correct
37 Correct 206 ms 166824 KB Output is correct
38 Incorrect 448 ms 191864 KB Output isn't correct
39 Incorrect 221 ms 166416 KB Output isn't correct
40 Incorrect 427 ms 190140 KB Output isn't correct
41 Correct 344 ms 188472 KB Output is correct
42 Incorrect 508 ms 193888 KB Output isn't correct