답안 #71435 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71435	2018-08-24T14:10:15 Z	someone_aa	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	1.11111 / 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, maxx;
vector<int>p[maxu];

void sieve() {
    memset(prime,true,sizeof(prime));
    prime[0] = prime[1] = false;
    for(int i=2;i<maxq;i++) {
        if(prime[i]) {
            for(int j=i;j<maxq;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;
       // maxx = max(maxx, primes[i] + 2);
    }

    for(int i=0;i<q;i++) {
        cin>>qi[i];
        maxq = max(maxq, qi[i] + 2);
    }
    solve();
    sieve();
    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
1.11111111111 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	243 ms	245128 KB	Output isn't correct
2	Incorrect	235 ms	245376 KB	Output isn't correct
3	Incorrect	238 ms	245524 KB	Output isn't correct
4	Incorrect	226 ms	245524 KB	Output isn't correct
5	Incorrect	216 ms	245524 KB	Output isn't correct
6	Incorrect	215 ms	245524 KB	Output isn't correct
7	Incorrect	241 ms	245544 KB	Output isn't correct
8	Incorrect	242 ms	245632 KB	Output isn't correct
9	Incorrect	240 ms	245632 KB	Output isn't correct
10	Incorrect	253 ms	245632 KB	Output isn't correct
11	Incorrect	231 ms	245776 KB	Output isn't correct
12	Correct	225 ms	245776 KB	Output is correct
13	Incorrect	232 ms	245932 KB	Output isn't correct
14	Incorrect	232 ms	246088 KB	Output isn't correct
15	Incorrect	230 ms	246088 KB	Output isn't correct
16	Incorrect	228 ms	246088 KB	Output isn't correct
17	Incorrect	248 ms	246088 KB	Output isn't correct
18	Incorrect	230 ms	246088 KB	Output isn't correct

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	829 ms	263168 KB	Time limit exceeded (wall clock)
2	Execution timed out	1032 ms	263168 KB	Time limit exceeded
3	Execution timed out	1016 ms	263168 KB	Time limit exceeded (wall clock)
4	Runtime error	874 ms	263168 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
5	Execution timed out	1064 ms	263168 KB	Time limit exceeded
6	Execution timed out	1088 ms	263168 KB	Time limit exceeded
7	Execution timed out	1037 ms	263168 KB	Time limit exceeded
8	Execution timed out	1082 ms	263168 KB	Time limit exceeded
9	Execution timed out	1072 ms	263168 KB	Time limit exceeded
10	Execution timed out	1035 ms	263168 KB	Time limit exceeded
11	Execution timed out	1068 ms	263168 KB	Time limit exceeded
12	Execution timed out	1060 ms	263168 KB	Time limit exceeded
13	Execution timed out	1038 ms	263168 KB	Time limit exceeded
14	Execution timed out	1032 ms	263168 KB	Time limit exceeded
15	Execution timed out	1086 ms	263168 KB	Time limit exceeded
16	Execution timed out	1076 ms	263168 KB	Time limit exceeded
17	Execution timed out	1020 ms	263168 KB	Time limit exceeded
18	Execution timed out	1053 ms	263168 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1034 ms	263168 KB	Time limit exceeded
2	Execution timed out	1044 ms	263168 KB	Time limit exceeded
3	Execution timed out	1049 ms	263168 KB	Time limit exceeded
4	Execution timed out	1028 ms	263168 KB	Time limit exceeded
5	Execution timed out	972 ms	263168 KB	Time limit exceeded (wall clock)
6	Execution timed out	1055 ms	263168 KB	Time limit exceeded
7	Execution timed out	1053 ms	263168 KB	Time limit exceeded
8	Execution timed out	1059 ms	263168 KB	Time limit exceeded
9	Execution timed out	1022 ms	263168 KB	Time limit exceeded
10	Execution timed out	1053 ms	263168 KB	Time limit exceeded
11	Execution timed out	1029 ms	263168 KB	Time limit exceeded
12	Execution timed out	1025 ms	263168 KB	Time limit exceeded
13	Execution timed out	1054 ms	263168 KB	Time limit exceeded
14	Execution timed out	1045 ms	263168 KB	Time limit exceeded
15	Execution timed out	1027 ms	263168 KB	Time limit exceeded
16	Execution timed out	1040 ms	263168 KB	Time limit exceeded
17	Execution timed out	1057 ms	263168 KB	Time limit exceeded
18	Execution timed out	1032 ms	263168 KB	Time limit exceeded
19	Execution timed out	1036 ms	263168 KB	Time limit exceeded
20	Execution timed out	1040 ms	263168 KB	Time limit exceeded
21	Execution timed out	1034 ms	263168 KB	Time limit exceeded
22	Execution timed out	1053 ms	263168 KB	Time limit exceeded
23	Execution timed out	1040 ms	263168 KB	Time limit exceeded
24	Execution timed out	1055 ms	263168 KB	Time limit exceeded
25	Execution timed out	1048 ms	263168 KB	Time limit exceeded
26	Execution timed out	1041 ms	263168 KB	Time limit exceeded
27	Execution timed out	1025 ms	263168 KB	Time limit exceeded
28	Execution timed out	1027 ms	263168 KB	Time limit exceeded
29	Execution timed out	1022 ms	263168 KB	Time limit exceeded
30	Execution timed out	1026 ms	263168 KB	Time limit exceeded
31	Execution timed out	1047 ms	263168 KB	Time limit exceeded
32	Execution timed out	1027 ms	263168 KB	Time limit exceeded
33	Execution timed out	1020 ms	263168 KB	Time limit exceeded
34	Execution timed out	1050 ms	263168 KB	Time limit exceeded
35	Execution timed out	1055 ms	263168 KB	Time limit exceeded
36	Execution timed out	1036 ms	263168 KB	Time limit exceeded
37	Execution timed out	1000 ms	263168 KB	Time limit exceeded (wall clock)
38	Execution timed out	1054 ms	263168 KB	Time limit exceeded
39	Execution timed out	1018 ms	263168 KB	Time limit exceeded
40	Execution timed out	1044 ms	263168 KB	Time limit exceeded
41	Execution timed out	1040 ms	263168 KB	Time limit exceeded
42	Execution timed out	1029 ms	263168 KB	Time limit exceeded

답안 #71435

Compilation message

Subtask #1 1.11111111111 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
1.11111111111 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0