oj.uz

Submission #631300

# Submission time Handle Problem Language Result Execution time Memory
631300 2022-08-18T02:57:45 Z socpite Brunhilda’s Birthday (BOI13_brunhilda) C++14
50.9524 / 100
 1000 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int mx = 1e7+5;
const int maxn = 1e5+5;

typedef long long ll;

ll lim = 1;

int m, q, ans;

int dp[mx], pp[mx], mm[mx];
vector<int> primes;
int l = 0, r = 0;
pair<int, int> que[maxn*130];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> q;
    for(int i = 2; i < mx; i++){
        if(!pp[i]){
            pp[i]=i;
            primes.push_back(i);
        }
        for(auto v: primes){
            if(i*v >= mx)break;
            pp[i*v]=v;
            if(i%v==0)break;
        }
    }
    while(m--){
        int x;
        cin >> x;
        if(!mm[x]){
            lim*=x;
            if(lim >= mx)lim = mx;
            que[r++]={0, x};
        }
        mm[x] = 1;
    }
    for(int i = 1; i < lim; i++){
        int tmp = i;
        while(que[l].f < i-(i%que[l].s)){
            l++;
        }
        dp[i] = dp[que[l].f]+1;
        while(pp[tmp]){
            int prv = pp[tmp];
            while(pp[tmp] == prv){
                tmp/=prv;
            }
            if(mm[prv])que[r++] = {i, prv};
        }
    }
    while(q--){
        int x;
        cin >> x;
        if(x >= lim)cout << "oo";
        else cout << dp[x];
        cout << "\n";
    }


}

Subtask #1
15.5555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 43724 KB Output is correct
2 Correct 784 ms 162008 KB Output is correct
3 Correct 128 ms 44820 KB Output is correct
4 Correct 675 ms 87460 KB Output is correct
5 Correct 701 ms 104768 KB Output is correct
6 Correct 122 ms 43604 KB Output is correct
7 Correct 136 ms 44900 KB Output is correct
8 Correct 173 ms 53632 KB Output is correct
9 Execution timed out 1027 ms 262144 KB Time limit exceeded
10 Execution timed out 1097 ms 222044 KB Time limit exceeded
11 Correct 799 ms 166668 KB Output is correct
12 Correct 677 ms 85636 KB Output is correct
13 Execution timed out 1089 ms 210944 KB Time limit exceeded
14 Execution timed out 1091 ms 211072 KB Time limit exceeded
15 Correct 749 ms 159656 KB Output is correct
16 Correct 742 ms 161912 KB Output is correct
17 Correct 681 ms 105148 KB Output is correct
18 Correct 641 ms 87392 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 98628 KB Output is correct
2 Correct 683 ms 135996 KB Output is correct
3 Execution timed out 1096 ms 208132 KB Time limit exceeded
4 Correct 722 ms 120316 KB Output is correct
5 Execution timed out 1022 ms 262144 KB Time limit exceeded
6 Correct 733 ms 137860 KB Output is correct
7 Correct 653 ms 98572 KB Output is correct
8 Correct 694 ms 115896 KB Output is correct
9 Execution timed out 1095 ms 220632 KB Time limit exceeded
10 Execution timed out 1086 ms 208184 KB Time limit exceeded
11 Execution timed out 1100 ms 208868 KB Time limit exceeded
12 Correct 860 ms 178424 KB Output is correct
13 Correct 677 ms 104280 KB Output is correct
14 Correct 725 ms 120216 KB Output is correct
15 Execution timed out 1089 ms 213404 KB Time limit exceeded
16 Correct 692 ms 135868 KB Output is correct
17 Execution timed out 1063 ms 211140 KB Time limit exceeded
18 Execution timed out 1095 ms 217964 KB Time limit exceeded

Subtask #3
24.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 211928 KB Time limit exceeded
2 Execution timed out 1098 ms 208416 KB Time limit exceeded
3 Execution timed out 1088 ms 208056 KB Time limit exceeded
4 Execution timed out 1073 ms 262144 KB Time limit exceeded
5 Correct 703 ms 118348 KB Output is correct
6 Execution timed out 1080 ms 215180 KB Time limit exceeded
7 Correct 828 ms 169292 KB Output is correct
8 Execution timed out 1086 ms 211864 KB Time limit exceeded
9 Execution timed out 1087 ms 212016 KB Time limit exceeded
10 Correct 888 ms 172460 KB Output is correct
11 Correct 790 ms 148684 KB Output is correct
12 Execution timed out 1100 ms 215980 KB Time limit exceeded
13 Execution timed out 1098 ms 211472 KB Time limit exceeded
14 Execution timed out 1107 ms 219784 KB Time limit exceeded
15 Execution timed out 1078 ms 211744 KB Time limit exceeded
16 Execution timed out 1097 ms 209804 KB Time limit exceeded
17 Execution timed out 1038 ms 262144 KB Time limit exceeded
18 Execution timed out 1097 ms 208436 KB Time limit exceeded
19 Correct 695 ms 120752 KB Output is correct
20 Execution timed out 1083 ms 208028 KB Time limit exceeded
21 Execution timed out 1105 ms 215548 KB Time limit exceeded
22 Execution timed out 1065 ms 208960 KB Time limit exceeded
23 Correct 715 ms 107724 KB Output is correct
24 Correct 690 ms 97548 KB Output is correct
25 Execution timed out 1076 ms 262144 KB Time limit exceeded
26 Execution timed out 1026 ms 262144 KB Time limit exceeded
27 Execution timed out 1081 ms 207052 KB Time limit exceeded
28 Correct 796 ms 114000 KB Output is correct
29 Execution timed out 1088 ms 262144 KB Time limit exceeded
30 Correct 937 ms 182876 KB Output is correct
31 Correct 754 ms 118664 KB Output is correct
32 Correct 773 ms 129820 KB Output is correct
33 Correct 645 ms 90988 KB Output is correct
34 Correct 829 ms 169248 KB Output is correct
35 Correct 695 ms 116016 KB Output is correct
36 Execution timed out 1099 ms 209324 KB Time limit exceeded
37 Correct 708 ms 118420 KB Output is correct
38 Execution timed out 1095 ms 215212 KB Time limit exceeded
39 Correct 741 ms 102388 KB Output is correct
40 Execution timed out 1095 ms 221260 KB Time limit exceeded
41 Correct 927 ms 194020 KB Output is correct
42 Execution timed out 1104 ms 209768 KB Time limit exceeded