답안 #631305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
631305	2022-08-18T03:02:15 Z	socpite	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	959 ms	155720 KB

brunhilda

#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], cnt[mx], pp[mx], mm[mx];
vector<int> primes;
int l = 0, r = 0;

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;
            cnt[0]++;
        }
        mm[x] = 1;
    }
    for(int i = 1; i < lim; i++){
        int tmp = i;
        while(pp[tmp]){
            int prv = pp[tmp];
            while(pp[tmp] == prv){
                tmp/=prv;
            }
            if(mm[prv]){
                cnt[i-prv]--;
                cnt[i]++;
            }
        }
        while(!cnt[r])r++;
        dp[i]=dp[r]+1;
    }
    while(q--){
        int x;
        cin >> x;
        if(x >= lim)cout << "oo";
        else cout << dp[x];
        cout << "\n";
    }


}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	115 ms	43632 KB	Output is correct
2	Correct	648 ms	120636 KB	Output is correct
3	Correct	130 ms	44256 KB	Output is correct
4	Correct	760 ms	120472 KB	Output is correct
5	Correct	579 ms	120472 KB	Output is correct
6	Correct	125 ms	43676 KB	Output is correct
7	Correct	178 ms	44276 KB	Output is correct
8	Correct	150 ms	49244 KB	Output is correct
9	Correct	624 ms	120544 KB	Output is correct
10	Correct	613 ms	120660 KB	Output is correct
11	Correct	592 ms	120516 KB	Output is correct
12	Correct	712 ms	120540 KB	Output is correct
13	Correct	708 ms	120588 KB	Output is correct
14	Correct	708 ms	120556 KB	Output is correct
15	Correct	609 ms	120508 KB	Output is correct
16	Correct	645 ms	120592 KB	Output is correct
17	Correct	615 ms	120524 KB	Output is correct
18	Correct	618 ms	120544 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	655 ms	124040 KB	Output is correct
2	Correct	689 ms	155656 KB	Output is correct
3	Correct	738 ms	124452 KB	Output is correct
4	Correct	661 ms	120820 KB	Output is correct
5	Correct	783 ms	125644 KB	Output is correct
6	Correct	611 ms	120736 KB	Output is correct
7	Correct	668 ms	124040 KB	Output is correct
8	Correct	611 ms	120648 KB	Output is correct
9	Correct	765 ms	125696 KB	Output is correct
10	Correct	697 ms	124436 KB	Output is correct
11	Correct	703 ms	122416 KB	Output is correct
12	Correct	667 ms	120720 KB	Output is correct
13	Correct	600 ms	122424 KB	Output is correct
14	Correct	649 ms	120848 KB	Output is correct
15	Correct	756 ms	123640 KB	Output is correct
16	Correct	662 ms	155720 KB	Output is correct
17	Correct	684 ms	120736 KB	Output is correct
18	Correct	780 ms	128568 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	767 ms	124612 KB	Output is correct
2	Correct	699 ms	123312 KB	Output is correct
3	Correct	689 ms	123180 KB	Output is correct
4	Correct	703 ms	121104 KB	Output is correct
5	Correct	702 ms	137976 KB	Output is correct
6	Correct	758 ms	121372 KB	Output is correct
7	Correct	762 ms	129680 KB	Output is correct
8	Correct	796 ms	124512 KB	Output is correct
9	Correct	800 ms	124480 KB	Output is correct
10	Correct	743 ms	120932 KB	Output is correct
11	Correct	720 ms	120928 KB	Output is correct
12	Correct	768 ms	120984 KB	Output is correct
13	Correct	789 ms	122268 KB	Output is correct
14	Correct	663 ms	121048 KB	Output is correct
15	Correct	768 ms	120960 KB	Output is correct
16	Correct	746 ms	120884 KB	Output is correct
17	Correct	793 ms	123676 KB	Output is correct
18	Correct	766 ms	123312 KB	Output is correct
19	Correct	722 ms	123256 KB	Output is correct
20	Correct	883 ms	123232 KB	Output is correct
21	Correct	704 ms	121100 KB	Output is correct
22	Correct	834 ms	126572 KB	Output is correct
23	Correct	853 ms	124632 KB	Output is correct
24	Correct	789 ms	121148 KB	Output is correct
25	Correct	833 ms	120980 KB	Output is correct
26	Correct	864 ms	121172 KB	Output is correct
27	Correct	774 ms	125620 KB	Output is correct
28	Correct	659 ms	121192 KB	Output is correct
29	Correct	911 ms	126508 KB	Output is correct
30	Correct	870 ms	124616 KB	Output is correct
31	Correct	760 ms	121864 KB	Output is correct
32	Correct	848 ms	121112 KB	Output is correct
33	Correct	656 ms	121500 KB	Output is correct
34	Correct	959 ms	129652 KB	Output is correct
35	Correct	687 ms	121128 KB	Output is correct
36	Correct	872 ms	126500 KB	Output is correct
37	Correct	766 ms	137996 KB	Output is correct
38	Correct	865 ms	121304 KB	Output is correct
39	Correct	757 ms	121304 KB	Output is correct
40	Correct	897 ms	121540 KB	Output is correct
41	Correct	928 ms	133456 KB	Output is correct
42	Correct	785 ms	120948 KB	Output is correct