oj.uz

Submission #816315

# Submission time Handle Problem Language Result Execution time Memory
816315 2023-08-09T04:47:27 Z QwertyPi Brunhilda’s Birthday (BOI13_brunhilda) C++14
19.3651 / 100
 706 ms 114120 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[1] = 0; c2[0] = n; cm = 0;
    for(int i = 2; 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;
        x = i;
        for(int i = 0; i < di; i++){
            c[lp[x]] = 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
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 78576 KB Output isn't correct
2 Incorrect 246 ms 78544 KB Output isn't correct
3 Incorrect 178 ms 78600 KB Output isn't correct
4 Correct 60 ms 78636 KB Output is correct
5 Correct 97 ms 78536 KB Output is correct
6 Incorrect 65 ms 78508 KB Output isn't correct
7 Incorrect 193 ms 78556 KB Output isn't correct
8 Incorrect 250 ms 78600 KB Output isn't correct
9 Incorrect 337 ms 78516 KB Output isn't correct
10 Incorrect 383 ms 78532 KB Output isn't correct
11 Incorrect 243 ms 78576 KB Output isn't correct
12 Correct 63 ms 78512 KB Output is correct
13 Correct 538 ms 78624 KB Output is correct
14 Incorrect 543 ms 78656 KB Output isn't correct
15 Incorrect 232 ms 78540 KB Output isn't correct
16 Incorrect 237 ms 78668 KB Output isn't correct
17 Incorrect 100 ms 78564 KB Output isn't correct
18 Correct 59 ms 78612 KB Output is correct

Subtask #2
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 82140 KB Output isn't correct
2 Correct 122 ms 114120 KB Output is correct
3 Correct 621 ms 82712 KB Output is correct
4 Incorrect 136 ms 78908 KB Output isn't correct
5 Correct 351 ms 83820 KB Output is correct
6 Incorrect 172 ms 78916 KB Output isn't correct
7 Incorrect 82 ms 82116 KB Output isn't correct
8 Incorrect 128 ms 78716 KB Output isn't correct
9 Incorrect 386 ms 83972 KB Output isn't correct
10 Correct 626 ms 82780 KB Output is correct
11 Incorrect 617 ms 80696 KB Output isn't correct
12 Incorrect 348 ms 78708 KB Output isn't correct
13 Incorrect 82 ms 80564 KB Output isn't correct
14 Incorrect 142 ms 78900 KB Output isn't correct
15 Correct 558 ms 81844 KB Output is correct
16 Correct 127 ms 114068 KB Output is correct
17 Incorrect 579 ms 78696 KB Output isn't correct
18 Incorrect 424 ms 86808 KB Output isn't correct

Subtask #3
7.14285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 617 ms 82664 KB Output isn't correct
2 Incorrect 642 ms 81580 KB Output isn't correct
3 Incorrect 660 ms 81476 KB Output isn't correct
4 Incorrect 367 ms 79108 KB Output isn't correct
5 Correct 152 ms 96408 KB Output is correct
6 Incorrect 511 ms 79288 KB Output isn't correct
7 Correct 269 ms 88112 KB Output is correct
8 Incorrect 576 ms 82756 KB Output isn't correct
9 Incorrect 562 ms 82780 KB Output isn't correct
10 Incorrect 326 ms 79004 KB Output isn't correct
11 Incorrect 224 ms 78952 KB Output isn't correct
12 Incorrect 509 ms 79024 KB Output isn't correct
13 Incorrect 534 ms 80400 KB Output isn't correct
14 Incorrect 419 ms 78736 KB Output isn't correct
15 Incorrect 614 ms 78936 KB Output isn't correct
16 Incorrect 593 ms 78908 KB Output isn't correct
17 Incorrect 366 ms 81924 KB Output isn't correct
18 Incorrect 706 ms 81488 KB Output isn't correct
19 Incorrect 117 ms 81412 KB Output isn't correct
20 Incorrect 630 ms 81380 KB Output isn't correct
21 Incorrect 468 ms 78768 KB Output isn't correct
22 Incorrect 622 ms 85020 KB Output isn't correct
23 Incorrect 137 ms 82812 KB Output isn't correct
24 Incorrect 106 ms 79148 KB Output isn't correct
25 Incorrect 337 ms 78988 KB Output isn't correct
26 Incorrect 363 ms 79140 KB Output isn't correct
27 Incorrect 680 ms 84172 KB Output isn't correct
28 Incorrect 140 ms 79136 KB Output isn't correct
29 Incorrect 399 ms 84928 KB Output isn't correct
30 Incorrect 325 ms 83024 KB Output isn't correct
31 Incorrect 158 ms 79920 KB Output isn't correct
32 Incorrect 194 ms 79088 KB Output isn't correct
33 Incorrect 90 ms 79568 KB Output isn't correct
34 Correct 280 ms 88012 KB Output is correct
35 Incorrect 131 ms 79136 KB Output isn't correct
36 Incorrect 653 ms 85012 KB Output isn't correct
37 Correct 144 ms 96416 KB Output is correct
38 Incorrect 523 ms 79276 KB Output isn't correct
39 Incorrect 128 ms 79272 KB Output isn't correct
40 Incorrect 422 ms 79560 KB Output isn't correct
41 Correct 352 ms 91936 KB Output is correct
42 Incorrect 598 ms 78848 KB Output isn't correct