oj.uz

Submission #816284

# Submission time Handle Problem Language Result Execution time Memory
816284 2023-08-09T04:41:30 Z QwertyPi Brunhilda’s Birthday (BOI13_brunhilda) C++14
94.9206 / 100
 1000 ms 114836 KB 
#include <bits/stdc++.h>
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;

void del(int p){
    c2[c[p]]--;
    while(cm < MAXN - 1 && c2[cm] == 0) cm++;
}

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[1] = 0; c2[0] = n; cm = 0;
    for(int i = 2; i < MAXN; i++){
        int x = i;
        while(lp[x] != 0){
            if(lp[x] != lp[x / lp[x]]){
                del(lp[x]);
            }
            x /= lp[x];
        }
        int cur = cm;
        x = i;
        while(lp[x] != 0){
            if(lp[x] != lp[x / lp[x]]){
                c[lp[x]] = cur + 1; c2[cur + 1]++;
            }
            x /= lp[x];
        }
        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:17:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   17 |     for(int i = 0; i < n; i++) cin >> p[i]; sort(p, p + n);
      |     ^~~
brunhilda.cpp:17:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   17 |     for(int i = 0; i < n; i++) cin >> p[i]; sort(p, p + n);
      |                                             ^~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 78648 KB Output is correct
2 Correct 409 ms 78708 KB Output is correct
3 Correct 305 ms 78656 KB Output is correct
4 Correct 73 ms 78688 KB Output is correct
5 Correct 130 ms 79220 KB Output is correct
6 Correct 83 ms 78632 KB Output is correct
7 Correct 294 ms 78692 KB Output is correct
8 Correct 436 ms 78736 KB Output is correct
9 Correct 524 ms 79648 KB Output is correct
10 Correct 585 ms 78944 KB Output is correct
11 Correct 336 ms 78960 KB Output is correct
12 Correct 77 ms 78524 KB Output is correct
13 Correct 839 ms 78552 KB Output is correct
14 Incorrect 826 ms 78616 KB Output isn't correct
15 Correct 382 ms 78632 KB Output is correct
16 Correct 385 ms 78668 KB Output is correct
17 Incorrect 106 ms 78672 KB Output isn't correct
18 Correct 65 ms 78676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 82156 KB Output is correct
2 Correct 169 ms 114824 KB Output is correct
3 Correct 963 ms 83160 KB Output is correct
4 Correct 176 ms 78932 KB Output is correct
5 Correct 545 ms 84124 KB Output is correct
6 Correct 287 ms 78868 KB Output is correct
7 Correct 98 ms 82244 KB Output is correct
8 Correct 134 ms 78640 KB Output is correct
9 Correct 566 ms 84388 KB Output is correct
10 Correct 999 ms 83196 KB Output is correct
11 Correct 941 ms 80944 KB Output is correct
12 Correct 449 ms 78696 KB Output is correct
13 Correct 90 ms 80484 KB Output is correct
14 Correct 159 ms 79004 KB Output is correct
15 Correct 804 ms 82088 KB Output is correct
16 Correct 157 ms 114836 KB Output is correct
17 Correct 849 ms 78664 KB Output is correct
18 Correct 643 ms 87532 KB Output is correct

Subtask #3
57.1428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 83356 KB Output is correct
2 Correct 932 ms 82096 KB Output is correct
3 Correct 977 ms 82316 KB Output is correct
4 Correct 563 ms 79832 KB Output is correct
5 Correct 166 ms 98060 KB Output is correct
6 Correct 733 ms 80152 KB Output is correct
7 Correct 340 ms 89204 KB Output is correct
8 Correct 883 ms 83344 KB Output is correct
9 Correct 909 ms 83384 KB Output is correct
10 Correct 371 ms 79060 KB Output is correct
11 Correct 268 ms 79192 KB Output is correct
12 Correct 711 ms 79164 KB Output is correct
13 Correct 800 ms 81464 KB Output is correct
14 Correct 608 ms 80188 KB Output is correct
15 Correct 819 ms 79168 KB Output is correct
16 Correct 914 ms 79136 KB Output is correct
17 Correct 522 ms 82312 KB Output is correct
18 Correct 957 ms 82108 KB Output is correct
19 Correct 180 ms 81580 KB Output is correct
20 Execution timed out 1029 ms 82248 KB Time limit exceeded
21 Correct 735 ms 79980 KB Output is correct
22 Correct 984 ms 86504 KB Output is correct
23 Correct 160 ms 83768 KB Output is correct
24 Correct 114 ms 79920 KB Output is correct
25 Correct 462 ms 79756 KB Output is correct
26 Correct 540 ms 79952 KB Output is correct
27 Execution timed out 1027 ms 85316 KB Time limit exceeded
28 Correct 136 ms 80052 KB Output is correct
29 Correct 501 ms 86508 KB Output is correct
30 Correct 428 ms 84208 KB Output is correct
31 Correct 166 ms 80628 KB Output is correct
32 Correct 217 ms 79948 KB Output is correct
33 Correct 116 ms 80300 KB Output is correct
34 Correct 362 ms 89232 KB Output is correct
35 Correct 161 ms 80012 KB Output is correct
36 Correct 947 ms 86380 KB Output is correct
37 Correct 168 ms 98060 KB Output is correct
38 Correct 717 ms 80052 KB Output is correct
39 Correct 132 ms 80080 KB Output is correct
40 Correct 633 ms 80356 KB Output is correct
41 Correct 508 ms 93128 KB Output is correct
42 Correct 865 ms 79868 KB Output is correct