답안 #63638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63638	2018-08-02T10:08:56 Z	Bodo171	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	100 / 100	803 ms	117788 KB

brunhilda

#include <iostream>
#include <fstream>

using namespace std;
const int nmax=10*1000*1000+5;
const int nm=10*1000*1000;
int d[nmax],pr[nmax];
int n,m,u,q,i,j,p,x;
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n>>q;
    for(i=1;i<=n;i++)
    {
        cin>>p;
        for(j=p;j<=nm;j+=p)
            pr[j]=p;
    }
    pr[0]=p;
    d[0]=1;
    for(i=0;i<=nm;i++)
        if(d[i])
    {
        for(j=u+1;j<min(i+pr[i],nm+1);j++)
            d[j]=d[i]+1;
        u=max(u,min(i+pr[i],nm+1)-1);
    }
    for(i=1;i<=q;i++)
    {
        cin>>x;
        if(!d[x]) {cout<<"oo\n";continue;}
        cout<<d[x]-1<<'\n';
    }
    return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	39544 KB	Output is correct
2	Correct	132 ms	78708 KB	Output is correct
3	Correct	71 ms	78708 KB	Output is correct
4	Correct	114 ms	78804 KB	Output is correct
5	Correct	132 ms	78924 KB	Output is correct
6	Correct	59 ms	78924 KB	Output is correct
7	Correct	69 ms	78924 KB	Output is correct
8	Correct	88 ms	78924 KB	Output is correct
9	Correct	181 ms	79000 KB	Output is correct
10	Correct	208 ms	79132 KB	Output is correct
11	Correct	200 ms	79132 KB	Output is correct
12	Correct	134 ms	79132 KB	Output is correct
13	Correct	379 ms	79132 KB	Output is correct
14	Correct	426 ms	79244 KB	Output is correct
15	Correct	179 ms	79244 KB	Output is correct
16	Correct	189 ms	79244 KB	Output is correct
17	Correct	212 ms	79268 KB	Output is correct
18	Correct	168 ms	79312 KB	Output is correct

Subtask #2

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	173 ms	79388 KB	Output is correct
2	Correct	214 ms	80084 KB	Output is correct
3	Correct	533 ms	80532 KB	Output is correct
4	Correct	152 ms	80532 KB	Output is correct
5	Correct	301 ms	80936 KB	Output is correct
6	Correct	128 ms	80936 KB	Output is correct
7	Correct	124 ms	81148 KB	Output is correct
8	Correct	151 ms	81148 KB	Output is correct
9	Correct	339 ms	81524 KB	Output is correct
10	Correct	435 ms	82064 KB	Output is correct
11	Correct	406 ms	82336 KB	Output is correct
12	Correct	204 ms	82336 KB	Output is correct
13	Correct	105 ms	82336 KB	Output is correct
14	Correct	151 ms	82336 KB	Output is correct
15	Correct	326 ms	82644 KB	Output is correct
16	Correct	173 ms	83344 KB	Output is correct
17	Correct	338 ms	83344 KB	Output is correct
18	Correct	350 ms	84072 KB	Output is correct

Subtask #3

60.0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	409 ms	84904 KB	Output is correct
2	Correct	472 ms	85316 KB	Output is correct
3	Correct	519 ms	86116 KB	Output is correct
4	Correct	487 ms	86920 KB	Output is correct
5	Correct	387 ms	88460 KB	Output is correct
6	Correct	501 ms	89348 KB	Output is correct
7	Correct	480 ms	90212 KB	Output is correct
8	Correct	367 ms	90904 KB	Output is correct
9	Correct	447 ms	91600 KB	Output is correct
10	Correct	290 ms	91688 KB	Output is correct
11	Correct	269 ms	91856 KB	Output is correct
12	Correct	377 ms	92152 KB	Output is correct
13	Correct	621 ms	93224 KB	Output is correct
14	Correct	449 ms	94288 KB	Output is correct
15	Correct	355 ms	94288 KB	Output is correct
16	Correct	414 ms	94328 KB	Output is correct
17	Correct	437 ms	94604 KB	Output is correct
18	Correct	598 ms	95132 KB	Output is correct
19	Correct	203 ms	95248 KB	Output is correct
20	Correct	538 ms	96340 KB	Output is correct
21	Correct	437 ms	97356 KB	Output is correct
22	Correct	721 ms	98396 KB	Output is correct
23	Correct	479 ms	99432 KB	Output is correct
24	Correct	374 ms	100376 KB	Output is correct
25	Correct	566 ms	101132 KB	Output is correct
26	Correct	490 ms	101720 KB	Output is correct
27	Correct	729 ms	102712 KB	Output is correct
28	Correct	395 ms	103684 KB	Output is correct
29	Correct	749 ms	105096 KB	Output is correct
30	Correct	688 ms	106328 KB	Output is correct
31	Correct	403 ms	107012 KB	Output is correct
32	Correct	451 ms	107748 KB	Output is correct
33	Correct	353 ms	108372 KB	Output is correct
34	Correct	506 ms	109452 KB	Output is correct
35	Correct	441 ms	110612 KB	Output is correct
36	Correct	803 ms	111892 KB	Output is correct
37	Correct	505 ms	113320 KB	Output is correct
38	Correct	634 ms	114176 KB	Output is correct
39	Correct	412 ms	115000 KB	Output is correct
40	Correct	555 ms	115780 KB	Output is correct
41	Correct	480 ms	116676 KB	Output is correct
42	Correct	702 ms	117788 KB	Output is correct