oj.uz

Submission #734612

# Submission time Handle Problem Language Result Execution time Memory
734612 2023-05-02T17:15:38 Z DAleksa Brunhilda’s Birthday (BOI13_brunhilda) C++17
9.84127 / 100
 525 ms 194408 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;
        if(dp[x] == -1) cout << "oo\n";
        else cout << dp[x] << "\n";
    }
    return 0;
}

Subtask #1
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 163524 KB Output isn't correct
2 Incorrect 218 ms 185316 KB Output isn't correct
3 Incorrect 204 ms 181368 KB Output isn't correct
4 Incorrect 149 ms 159832 KB Output isn't correct
5 Incorrect 189 ms 167368 KB Output isn't correct
6 Incorrect 169 ms 163636 KB Output isn't correct
7 Incorrect 215 ms 181392 KB Output isn't correct
8 Incorrect 222 ms 186356 KB Output isn't correct
9 Incorrect 258 ms 189092 KB Output isn't correct
10 Incorrect 311 ms 190056 KB Output isn't correct
11 Incorrect 280 ms 184344 KB Output isn't correct
12 Correct 117 ms 159028 KB Output is correct
13 Correct 402 ms 193320 KB Output is correct
14 Incorrect 393 ms 193420 KB Output isn't correct
15 Incorrect 246 ms 184572 KB Output isn't correct
16 Incorrect 207 ms 185340 KB Output isn't correct
17 Incorrect 190 ms 167372 KB Output isn't correct
18 Incorrect 125 ms 159928 KB Output isn't correct

Subtask #2
3.33333333333 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 150 ms 163644 KB Output isn't correct
2 Incorrect 190 ms 166116 KB Output isn't correct
3 Incorrect 435 ms 194056 KB Output isn't correct
4 Incorrect 229 ms 172744 KB Output isn't correct
5 Incorrect 356 ms 188420 KB Output isn't correct
6 Incorrect 219 ms 180432 KB Output isn't correct
7 Incorrect 164 ms 163552 KB Output isn't correct
8 Incorrect 222 ms 171140 KB Output isn't correct
9 Correct 370 ms 190568 KB Output is correct
10 Incorrect 440 ms 194024 KB Output isn't correct
11 Incorrect 403 ms 193680 KB Output isn't correct
12 Incorrect 324 ms 186752 KB Output isn't correct
13 Correct 147 ms 166556 KB Output is correct
14 Incorrect 232 ms 172876 KB Output isn't correct
15 Correct 422 ms 192724 KB Output is correct
16 Incorrect 179 ms 166124 KB Output isn't correct
17 Incorrect 396 ms 192920 KB Output isn't correct
18 Incorrect 379 ms 191352 KB Output isn't correct

Subtask #3
4.28571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 378 ms 193372 KB Output isn't correct
2 Incorrect 468 ms 193896 KB Output isn't correct
3 Incorrect 474 ms 193964 KB Output isn't correct
4 Incorrect 364 ms 188332 KB Output isn't correct
5 Correct 220 ms 166856 KB Output is correct
6 Incorrect 437 ms 191732 KB Output isn't correct
7 Incorrect 356 ms 185264 KB Output isn't correct
8 Incorrect 411 ms 193332 KB Output isn't correct
9 Incorrect 412 ms 193388 KB Output isn't correct
10 Incorrect 327 ms 184184 KB Output isn't correct
11 Incorrect 316 ms 180180 KB Output isn't correct
12 Incorrect 374 ms 191648 KB Output isn't correct
13 Incorrect 453 ms 192716 KB Output isn't correct
14 Incorrect 324 ms 191304 KB Output isn't correct
15 Incorrect 420 ms 193204 KB Output isn't correct
16 Incorrect 428 ms 193380 KB Output isn't correct
17 Incorrect 362 ms 189316 KB Output isn't correct
18 Incorrect 445 ms 193860 KB Output isn't correct
19 Incorrect 177 ms 173476 KB Output isn't correct
20 Incorrect 431 ms 193968 KB Output isn't correct
21 Incorrect 346 ms 192624 KB Output isn't correct
22 Incorrect 525 ms 194408 KB Output isn't correct
23 Incorrect 247 ms 168056 KB Output isn't correct
24 Incorrect 185 ms 164320 KB Output isn't correct
25 Incorrect 367 ms 187072 KB Output isn't correct
26 Incorrect 337 ms 188336 KB Output isn't correct
27 Incorrect 462 ms 194404 KB Output isn't correct
28 Incorrect 198 ms 171128 KB Output isn't correct
29 Incorrect 449 ms 191220 KB Output isn't correct
30 Incorrect 412 ms 189448 KB Output isn't correct
31 Incorrect 241 ms 172040 KB Output isn't correct
32 Incorrect 274 ms 175820 KB Output isn't correct
33 Incorrect 154 ms 161420 KB Output isn't correct
34 Incorrect 365 ms 185180 KB Output isn't correct
35 Incorrect 211 ms 171764 KB Output isn't correct
36 Incorrect 476 ms 194260 KB Output isn't correct
37 Correct 217 ms 166868 KB Output is correct
38 Incorrect 412 ms 191800 KB Output isn't correct
39 Incorrect 220 ms 166424 KB Output isn't correct
40 Incorrect 392 ms 190280 KB Output isn't correct
41 Correct 325 ms 188416 KB Output is correct
42 Incorrect 425 ms 193972 KB Output isn't correct