oj.uz

답안 #816322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
816322 2023-08-09T04:48:56 Z QwertyPi Brunhilda’s Birthday (BOI13_brunhilda) C++14
97.7778 / 100
 767 ms 114140 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;
        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
17.7777777778 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 96 ms 78680 KB Output is correct
2 Correct 284 ms 78668 KB Output is correct
3 Correct 186 ms 78624 KB Output is correct
4 Correct 66 ms 78620 KB Output is correct
5 Correct 137 ms 79148 KB Output is correct
6 Correct 81 ms 78652 KB Output is correct
7 Correct 195 ms 78660 KB Output is correct
8 Correct 298 ms 78700 KB Output is correct
9 Correct 424 ms 79632 KB Output is correct
10 Correct 502 ms 78864 KB Output is correct
11 Correct 297 ms 78932 KB Output is correct
12 Correct 57 ms 78556 KB Output is correct
13 Correct 626 ms 78604 KB Output is correct
14 Incorrect 645 ms 78564 KB Output isn't correct
15 Correct 308 ms 78620 KB Output is correct
16 Correct 282 ms 78620 KB Output is correct
17 Incorrect 116 ms 78676 KB Output isn't correct
18 Correct 60 ms 78584 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 82128 KB Output is correct
2 Correct 132 ms 114084 KB Output is correct
3 Correct 689 ms 82768 KB Output is correct
4 Correct 152 ms 78916 KB Output is correct
5 Correct 420 ms 83808 KB Output is correct
6 Correct 221 ms 78884 KB Output is correct
7 Correct 89 ms 82136 KB Output is correct
8 Correct 153 ms 78664 KB Output is correct
9 Correct 393 ms 83892 KB Output is correct
10 Correct 645 ms 82764 KB Output is correct
11 Correct 632 ms 80720 KB Output is correct
12 Correct 340 ms 78716 KB Output is correct
13 Correct 93 ms 80552 KB Output is correct
14 Correct 157 ms 78884 KB Output is correct
15 Correct 557 ms 81852 KB Output is correct
16 Correct 131 ms 114140 KB Output is correct
17 Correct 574 ms 78732 KB Output is correct
18 Correct 468 ms 86840 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 644 ms 82700 KB Output is correct
2 Correct 630 ms 81540 KB Output is correct
3 Correct 645 ms 81484 KB Output is correct
4 Correct 383 ms 79180 KB Output is correct
5 Correct 155 ms 96532 KB Output is correct
6 Correct 521 ms 79300 KB Output is correct
7 Correct 298 ms 87996 KB Output is correct
8 Correct 641 ms 82720 KB Output is correct
9 Correct 577 ms 82764 KB Output is correct
10 Correct 307 ms 79028 KB Output is correct
11 Correct 244 ms 79072 KB Output is correct
12 Correct 497 ms 79040 KB Output is correct
13 Correct 547 ms 80460 KB Output is correct
14 Correct 488 ms 79492 KB Output is correct
15 Correct 583 ms 78968 KB Output is correct
16 Correct 610 ms 78944 KB Output is correct
17 Correct 512 ms 81868 KB Output is correct
18 Correct 680 ms 81492 KB Output is correct
19 Correct 142 ms 81348 KB Output is correct
20 Correct 683 ms 81532 KB Output is correct
21 Correct 549 ms 79264 KB Output is correct
22 Correct 696 ms 84948 KB Output is correct
23 Correct 154 ms 82828 KB Output is correct
24 Correct 119 ms 79276 KB Output is correct
25 Correct 369 ms 79076 KB Output is correct
26 Correct 418 ms 79220 KB Output is correct
27 Correct 767 ms 84076 KB Output is correct
28 Correct 177 ms 79292 KB Output is correct
29 Correct 421 ms 84980 KB Output is correct
30 Correct 339 ms 82980 KB Output is correct
31 Correct 171 ms 80016 KB Output is correct
32 Correct 201 ms 79232 KB Output is correct
33 Correct 96 ms 79640 KB Output is correct
34 Correct 310 ms 88112 KB Output is correct
35 Correct 151 ms 79308 KB Output is correct
36 Correct 684 ms 84988 KB Output is correct
37 Correct 155 ms 96492 KB Output is correct
38 Correct 618 ms 79304 KB Output is correct
39 Correct 137 ms 79288 KB Output is correct
40 Correct 483 ms 79588 KB Output is correct
41 Correct 405 ms 91996 KB Output is correct
42 Correct 698 ms 79116 KB Output is correct