oj.uz

Submission #83515

# Submission time Handle Problem Language Result Execution time Memory
83515 2018-11-08T16:56:23 Z teomrn Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 419 ms 117776 KB 
#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100010, VMAX = 10000000;
int prime[NMAX + 10];
int lower[VMAX + 10];
int dist[VMAX + 10];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int m, q;
    cin >> m >> q;

    while (m--) {
        int x;
        cin >> x;
        for (int i = 0; i <= VMAX; i += x)
            lower[i] = x;
    }

    int act = 0, until = 0, next = 0;
    for (int i = 0; i <= VMAX; i++) {
        if (i > until)
            until = next, act++;
        if (until < i)
            break;
        dist[i] = act;
        if (lower[i])
            next = max(next, i + lower[i] - 1);
    }

    while (q--) {
        int x;
        cin >> x;
        if (dist[x])
            cout << dist[x] << '\n';
        else
            cout << "oo\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 39544 KB Output is correct
2 Correct 126 ms 78672 KB Output is correct
3 Correct 61 ms 78672 KB Output is correct
4 Correct 95 ms 78948 KB Output is correct
5 Correct 133 ms 78996 KB Output is correct
6 Correct 44 ms 78996 KB Output is correct
7 Correct 57 ms 78996 KB Output is correct
8 Correct 69 ms 78996 KB Output is correct
9 Correct 151 ms 79176 KB Output is correct
10 Correct 174 ms 79176 KB Output is correct
11 Correct 183 ms 79176 KB Output is correct
12 Correct 92 ms 79176 KB Output is correct
13 Correct 301 ms 79232 KB Output is correct
14 Correct 302 ms 79256 KB Output is correct
15 Correct 158 ms 79256 KB Output is correct
16 Correct 127 ms 79256 KB Output is correct
17 Correct 151 ms 79420 KB Output is correct
18 Correct 95 ms 79420 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 79420 KB Output is correct
2 Correct 159 ms 80108 KB Output is correct
3 Correct 388 ms 80708 KB Output is correct
4 Correct 182 ms 80708 KB Output is correct
5 Correct 270 ms 80944 KB Output is correct
6 Correct 135 ms 81048 KB Output is correct
7 Correct 134 ms 81052 KB Output is correct
8 Correct 177 ms 81136 KB Output is correct
9 Correct 308 ms 81656 KB Output is correct
10 Correct 380 ms 82144 KB Output is correct
11 Correct 363 ms 82368 KB Output is correct
12 Correct 212 ms 82376 KB Output is correct
13 Correct 113 ms 82376 KB Output is correct
14 Correct 185 ms 82408 KB Output is correct
15 Correct 316 ms 82700 KB Output is correct
16 Correct 158 ms 83348 KB Output is correct
17 Correct 307 ms 83348 KB Output is correct
18 Correct 308 ms 84200 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 84840 KB Output is correct
2 Correct 392 ms 85444 KB Output is correct
3 Correct 392 ms 86236 KB Output is correct
4 Correct 248 ms 87048 KB Output is correct
5 Correct 189 ms 88460 KB Output is correct
6 Correct 322 ms 89268 KB Output is correct
7 Correct 315 ms 90248 KB Output is correct
8 Correct 311 ms 91016 KB Output is correct
9 Correct 310 ms 91556 KB Output is correct
10 Correct 266 ms 91704 KB Output is correct
11 Correct 239 ms 91848 KB Output is correct
12 Correct 294 ms 92136 KB Output is correct
13 Correct 375 ms 93164 KB Output is correct
14 Correct 223 ms 94188 KB Output is correct
15 Correct 301 ms 94188 KB Output is correct
16 Correct 344 ms 94268 KB Output is correct
17 Correct 330 ms 94732 KB Output is correct
18 Correct 406 ms 95236 KB Output is correct
19 Correct 127 ms 95364 KB Output is correct
20 Correct 400 ms 96248 KB Output is correct
21 Correct 249 ms 97516 KB Output is correct
22 Correct 399 ms 98572 KB Output is correct
23 Correct 197 ms 99564 KB Output is correct
24 Correct 158 ms 100252 KB Output is correct
25 Correct 283 ms 101044 KB Output is correct
26 Correct 243 ms 101776 KB Output is correct
27 Correct 419 ms 102732 KB Output is correct
28 Correct 157 ms 103716 KB Output is correct
29 Correct 386 ms 105028 KB Output is correct
30 Correct 370 ms 106344 KB Output is correct
31 Correct 205 ms 107116 KB Output is correct
32 Correct 219 ms 107848 KB Output is correct
33 Correct 126 ms 108548 KB Output is correct
34 Correct 301 ms 109508 KB Output is correct
35 Correct 174 ms 110712 KB Output is correct
36 Correct 387 ms 111984 KB Output is correct
37 Correct 200 ms 113376 KB Output is correct
38 Correct 323 ms 114264 KB Output is correct
39 Correct 178 ms 115132 KB Output is correct
40 Correct 278 ms 115932 KB Output is correct
41 Correct 266 ms 116756 KB Output is correct
42 Correct 353 ms 117776 KB Output is correct