oj.uz

Submission #816335

# Submission time Handle Problem Language Result Execution time Memory
816335 2023-08-09T04:51:48 Z QwertyPi Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 738 ms 114124 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
using namespace std;

const int MAXN = 1e7 + 11;
const int MAXM = 1e5 + 11;
int p[MAXM];
int lp[MAXN], dp[MAXN], c[MAXN], c2[MAXN], cm = 0;

int d[100], di = 0;
int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    int n, Q; cin >> n >> Q;
    for(int i = 0; i < n; i++) cin >> p[i]; sort(p, p + n);
    for(int i = 0; i < n; i++){
        for(int j = p[i]; j < MAXN; j += p[i]){
            if(!lp[j]) lp[j] = p[i];
        }
    }

    dp[0] = 0; c2[0] = n; cm = 0;
    for(int i = 1; i < MAXN; i++){
        int x = i;
        di = 0;
        while(lp[x] != 0){
            if(lp[x] != lp[x / lp[x]]) d[di++] = lp[x];
            x /= lp[x];
        }

        for(int i = 0; i < di; i++){
            c2[c[d[i]]]--;
            while(cm < MAXN - 1 && c2[cm] == 0) cm++;
        }
        int cur = cm;
        for(int i = 0; i < di; i++){
            c[d[i]] = cur + 1; c2[cur + 1]++;
        }
        dp[i] = cur + 1;
    }
    for(int i = 0; i < Q; i++){
        int k; cin >> k; cout << (dp[k] != MAXN ? to_string(dp[k]) : "oo") << '\n';
    }
}

Compilation message

brunhilda.cpp: In function 'int32_t main()':
brunhilda.cpp:15:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   15 |     for(int i = 0; i < n; i++) cin >> p[i]; sort(p, p + n);
      |     ^~~
brunhilda.cpp:15:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   15 |     for(int i = 0; i < n; i++) cin >> p[i]; sort(p, p + n);
      |                                             ^~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 78608 KB Output is correct
2 Correct 278 ms 78636 KB Output is correct
3 Correct 196 ms 78740 KB Output is correct
4 Correct 67 ms 78540 KB Output is correct
5 Correct 127 ms 79180 KB Output is correct
6 Correct 76 ms 78668 KB Output is correct
7 Correct 186 ms 78668 KB Output is correct
8 Correct 311 ms 78760 KB Output is correct
9 Correct 400 ms 79604 KB Output is correct
10 Correct 436 ms 78896 KB Output is correct
11 Correct 288 ms 78900 KB Output is correct
12 Correct 72 ms 78620 KB Output is correct
13 Correct 591 ms 78628 KB Output is correct
14 Correct 622 ms 78632 KB Output is correct
15 Correct 302 ms 78668 KB Output is correct
16 Correct 285 ms 78616 KB Output is correct
17 Correct 116 ms 78604 KB Output is correct
18 Correct 65 ms 78540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 82124 KB Output is correct
2 Correct 136 ms 114124 KB Output is correct
3 Correct 719 ms 82744 KB Output is correct
4 Correct 161 ms 79016 KB Output is correct
5 Correct 357 ms 83864 KB Output is correct
6 Correct 198 ms 78832 KB Output is correct
7 Correct 104 ms 82100 KB Output is correct
8 Correct 145 ms 78632 KB Output is correct
9 Correct 438 ms 83964 KB Output is correct
10 Correct 644 ms 82712 KB Output is correct
11 Correct 629 ms 80724 KB Output is correct
12 Correct 334 ms 78724 KB Output is correct
13 Correct 92 ms 80464 KB Output is correct
14 Correct 149 ms 78924 KB Output is correct
15 Correct 523 ms 81796 KB Output is correct
16 Correct 135 ms 114124 KB Output is correct
17 Correct 582 ms 78632 KB Output is correct
18 Correct 434 ms 86784 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 82768 KB Output is correct
2 Correct 618 ms 81560 KB Output is correct
3 Correct 640 ms 81460 KB Output is correct
4 Correct 453 ms 79200 KB Output is correct
5 Correct 170 ms 96428 KB Output is correct
6 Correct 560 ms 79388 KB Output is correct
7 Correct 308 ms 88048 KB Output is correct
8 Correct 583 ms 82724 KB Output is correct
9 Correct 738 ms 82784 KB Output is correct
10 Correct 415 ms 78956 KB Output is correct
11 Correct 258 ms 79020 KB Output is correct
12 Correct 512 ms 79052 KB Output is correct
13 Correct 562 ms 80548 KB Output is correct
14 Correct 532 ms 79492 KB Output is correct
15 Correct 612 ms 79020 KB Output is correct
16 Correct 621 ms 78888 KB Output is correct
17 Correct 432 ms 81848 KB Output is correct
18 Correct 647 ms 81548 KB Output is correct
19 Correct 123 ms 81340 KB Output is correct
20 Correct 696 ms 81512 KB Output is correct
21 Correct 536 ms 79196 KB Output is correct
22 Correct 695 ms 84948 KB Output is correct
23 Correct 143 ms 82860 KB Output is correct
24 Correct 114 ms 79176 KB Output is correct
25 Correct 375 ms 79124 KB Output is correct
26 Correct 388 ms 79180 KB Output is correct
27 Correct 694 ms 84092 KB Output is correct
28 Correct 129 ms 79212 KB Output is correct
29 Correct 391 ms 85028 KB Output is correct
30 Correct 326 ms 83060 KB Output is correct
31 Correct 167 ms 79944 KB Output is correct
32 Correct 230 ms 79228 KB Output is correct
33 Correct 95 ms 79624 KB Output is correct
34 Correct 323 ms 88056 KB Output is correct
35 Correct 147 ms 79304 KB Output is correct
36 Correct 732 ms 84980 KB Output is correct
37 Correct 150 ms 96516 KB Output is correct
38 Correct 527 ms 79380 KB Output is correct
39 Correct 132 ms 79320 KB Output is correct
40 Correct 486 ms 79560 KB Output is correct
41 Correct 415 ms 91936 KB Output is correct
42 Correct 668 ms 79108 KB Output is correct