oj.uz

Submission #63638

# Submission time Handle Problem Language Result Execution time Memory
63638 2018-08-02T10:08:56 Z Bodo171 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 803 ms 117788 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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