답안 #71433 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71433	2018-08-24T14:05:15 Z	someone_aa	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	0 / 100	1000 ms	263168 KB

brunhilda

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxu = 10000100;
const int maxn = 100100;
bool prime[maxu], exist[maxu];
int primes[maxn], qi[maxn], dp[maxu], n, m, q;
int ind[maxn], tree[4*maxn], maxq, inf;
vector<int>p[maxu];

void sieve() {
    memset(prime,true,sizeof(prime));
    prime[0] = prime[1] = false;
    for(int i=2;i<maxu;i++) {
        if(prime[i]) {
            for(int j=i;j<maxu;j+=i) {
                if(exist[i])
                    p[j].pb(ind[i]);
                if(j > i) prime[j] = false;
            }
        }
    }
}

void update(int x, int val, int li=0, int ri=n-1, int index=1) {
    if(li==ri) tree[index] = val;
    else {
        int mid = (li+ri)/2;
        if(x <= mid) update(x,val,li,mid,2*index);
        else if(x>mid) update(x,val,mid+1,ri,2*index+1);
        tree[index] = min(tree[2*index], tree[2*index+1]);
    }
}

void solve() {
    inf = 1000000000;
    for(int i=1;i<=maxq;i++) {
        for(int j:p[i]) {
            update(j, inf);
        }
        dp[i] = tree[1] + 1;
        for(int j:p[i]) {
            update(j, dp[i]);
        }
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=0;i<n;i++) {
        cin>>primes[i];
        exist[primes[i]] = true;
        ind[primes[i]] = i;
    }

    sieve();
    for(int i=0;i<q;i++) {
        cin>>qi[i];
        maxq = max(maxq, qi[i]);
    }
    solve();
    for(int i=0;i<q;i++) {
        if(dp[qi[i]] >= inf) cout<<"oo\n";
        else cout<<dp[qi[i]]<<"\n";
    }
    return 0;
}

Subtask #1
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1037 ms	263168 KB	Time limit exceeded
2	Execution timed out	1039 ms	263168 KB	Time limit exceeded
3	Execution timed out	1043 ms	263168 KB	Time limit exceeded
4	Runtime error	979 ms	263168 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
5	Execution timed out	1048 ms	263168 KB	Time limit exceeded
6	Execution timed out	1018 ms	263168 KB	Time limit exceeded
7	Execution timed out	1051 ms	263168 KB	Time limit exceeded
8	Execution timed out	1046 ms	263168 KB	Time limit exceeded
9	Execution timed out	1049 ms	263168 KB	Time limit exceeded
10	Execution timed out	1040 ms	263168 KB	Time limit exceeded
11	Execution timed out	1026 ms	263168 KB	Time limit exceeded
12	Runtime error	542 ms	263168 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
13	Execution timed out	1054 ms	263168 KB	Time limit exceeded
14	Execution timed out	1051 ms	263168 KB	Time limit exceeded
15	Execution timed out	1050 ms	263168 KB	Time limit exceeded
16	Execution timed out	1048 ms	263168 KB	Time limit exceeded
17	Execution timed out	1018 ms	263168 KB	Time limit exceeded
18	Runtime error	950 ms	263168 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1029 ms	263168 KB	Time limit exceeded
2	Execution timed out	1029 ms	263168 KB	Time limit exceeded
3	Execution timed out	1051 ms	263168 KB	Time limit exceeded
4	Execution timed out	1052 ms	263168 KB	Time limit exceeded
5	Execution timed out	1026 ms	263168 KB	Time limit exceeded
6	Execution timed out	1040 ms	263168 KB	Time limit exceeded
7	Execution timed out	1048 ms	263168 KB	Time limit exceeded
8	Execution timed out	1034 ms	263168 KB	Time limit exceeded
9	Execution timed out	1037 ms	263168 KB	Time limit exceeded
10	Execution timed out	1062 ms	263168 KB	Time limit exceeded
11	Execution timed out	1066 ms	263168 KB	Time limit exceeded
12	Execution timed out	1041 ms	263168 KB	Time limit exceeded
13	Execution timed out	1052 ms	263168 KB	Time limit exceeded
14	Execution timed out	1046 ms	263168 KB	Time limit exceeded
15	Execution timed out	1033 ms	263168 KB	Time limit exceeded
16	Execution timed out	1041 ms	263168 KB	Time limit exceeded
17	Execution timed out	1046 ms	263168 KB	Time limit exceeded
18	Execution timed out	1022 ms	263168 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1062 ms	263168 KB	Time limit exceeded
2	Execution timed out	1071 ms	263168 KB	Time limit exceeded
3	Execution timed out	1020 ms	263168 KB	Time limit exceeded
4	Execution timed out	1055 ms	263168 KB	Time limit exceeded
5	Execution timed out	1047 ms	263168 KB	Time limit exceeded
6	Execution timed out	1049 ms	263168 KB	Time limit exceeded
7	Execution timed out	1041 ms	263168 KB	Time limit exceeded
8	Execution timed out	1027 ms	263168 KB	Time limit exceeded
9	Execution timed out	1030 ms	263168 KB	Time limit exceeded
10	Execution timed out	1033 ms	263168 KB	Time limit exceeded
11	Execution timed out	1042 ms	263168 KB	Time limit exceeded
12	Execution timed out	1051 ms	263168 KB	Time limit exceeded
13	Execution timed out	1063 ms	263168 KB	Time limit exceeded
14	Execution timed out	1040 ms	263168 KB	Time limit exceeded
15	Execution timed out	1056 ms	263168 KB	Time limit exceeded
16	Execution timed out	1054 ms	263168 KB	Time limit exceeded
17	Execution timed out	1051 ms	263168 KB	Time limit exceeded
18	Execution timed out	1052 ms	263168 KB	Time limit exceeded
19	Execution timed out	1020 ms	263168 KB	Time limit exceeded
20	Execution timed out	1037 ms	263168 KB	Time limit exceeded
21	Execution timed out	1049 ms	263168 KB	Time limit exceeded
22	Execution timed out	1047 ms	263168 KB	Time limit exceeded
23	Execution timed out	1031 ms	263168 KB	Time limit exceeded
24	Execution timed out	1034 ms	263168 KB	Time limit exceeded
25	Execution timed out	1040 ms	263168 KB	Time limit exceeded
26	Execution timed out	1029 ms	263168 KB	Time limit exceeded
27	Execution timed out	1022 ms	263168 KB	Time limit exceeded
28	Execution timed out	1027 ms	263168 KB	Time limit exceeded
29	Execution timed out	1044 ms	263168 KB	Time limit exceeded
30	Execution timed out	1026 ms	263168 KB	Time limit exceeded
31	Execution timed out	1025 ms	263168 KB	Time limit exceeded
32	Execution timed out	1054 ms	263168 KB	Time limit exceeded
33	Execution timed out	1040 ms	263168 KB	Time limit exceeded
34	Execution timed out	1029 ms	263168 KB	Time limit exceeded
35	Execution timed out	1050 ms	263168 KB	Time limit exceeded
36	Execution timed out	1024 ms	263168 KB	Time limit exceeded
37	Execution timed out	1061 ms	263168 KB	Time limit exceeded
38	Execution timed out	1055 ms	263168 KB	Time limit exceeded
39	Execution timed out	1039 ms	263168 KB	Time limit exceeded
40	Execution timed out	1032 ms	263168 KB	Time limit exceeded
41	Execution timed out	1062 ms	263168 KB	Time limit exceeded
42	Execution timed out	1059 ms	263168 KB	Time limit exceeded

답안 #71433

Compilation message

Subtask #1 0 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
0 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0