oj.uz

Submission #155753

# Submission time Handle Problem Language Result Execution time Memory
155753 2019-09-30T09:11:33 Z EntityIT Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 486 ms 79224 KB 
#include<bits/stdc++.h>

using namespace std;

using LL = long long;
const int NPrime = (int)1e5 + 5, NQuery = NPrime, MAX = (int)1e7 + 5;
int nPrime, nQuery, maxPrime[MAX], f[MAX], LIM = 1;

int main() {
    scanf(" %d %d", &nPrime, &nQuery);
    for (int i = 1; i <= nPrime; ++i) {
        int p; scanf(" %d", &p);
        LIM = (int)min( (LL)MAX, (LL)LIM * p);
        for (int j = 0; j < MAX; j += p) maxPrime[j] = p;
    }

    int lst = 0, nxt = lst;
    for (int i = 0; i < LIM; ++i) {
        nxt = max(nxt, i + maxPrime[i] - 1);
        f[i + 1] = f[i];
        if (i == lst) {
            ++f[i + 1];
            lst = nxt;
        }
    }

    while (nQuery--) {
        int inp; scanf(" %d", &inp);
        if (inp >= LIM) printf("oo\n");
        else printf("%d\n", f[inp]);
    }

    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:10:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %d %d", &nPrime, &nQuery);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:12:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int p; scanf(" %d", &p);
                ~~~~~^~~~~~~~~~~
brunhilda.cpp:28:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int inp; scanf(" %d", &inp);
                  ~~~~~^~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 39544 KB Output is correct
2 Correct 121 ms 78772 KB Output is correct
3 Correct 58 ms 40568 KB Output is correct
4 Correct 96 ms 78584 KB Output is correct
5 Correct 109 ms 78584 KB Output is correct
6 Correct 43 ms 39416 KB Output is correct
7 Correct 54 ms 40568 KB Output is correct
8 Correct 64 ms 42980 KB Output is correct
9 Correct 135 ms 78668 KB Output is correct
10 Correct 157 ms 78544 KB Output is correct
11 Correct 153 ms 78584 KB Output is correct
12 Correct 100 ms 78652 KB Output is correct
13 Correct 330 ms 78608 KB Output is correct
14 Correct 272 ms 78580 KB Output is correct
15 Correct 131 ms 78584 KB Output is correct
16 Correct 146 ms 78536 KB Output is correct
17 Correct 133 ms 78604 KB Output is correct
18 Correct 95 ms 78584 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 78584 KB Output is correct
2 Correct 136 ms 78584 KB Output is correct
3 Correct 329 ms 78584 KB Output is correct
4 Correct 141 ms 78584 KB Output is correct
5 Correct 286 ms 78540 KB Output is correct
6 Correct 119 ms 78584 KB Output is correct
7 Correct 111 ms 78636 KB Output is correct
8 Correct 138 ms 78656 KB Output is correct
9 Correct 280 ms 78712 KB Output is correct
10 Correct 341 ms 78584 KB Output is correct
11 Correct 337 ms 78556 KB Output is correct
12 Correct 182 ms 78584 KB Output is correct
13 Correct 100 ms 78584 KB Output is correct
14 Correct 140 ms 78732 KB Output is correct
15 Correct 274 ms 78536 KB Output is correct
16 Correct 136 ms 78584 KB Output is correct
17 Correct 284 ms 78776 KB Output is correct
18 Correct 275 ms 78584 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 78712 KB Output is correct
2 Correct 370 ms 78588 KB Output is correct
3 Correct 455 ms 78712 KB Output is correct
4 Correct 267 ms 78840 KB Output is correct
5 Correct 211 ms 78916 KB Output is correct
6 Correct 308 ms 78860 KB Output is correct
7 Correct 267 ms 78968 KB Output is correct
8 Correct 356 ms 78684 KB Output is correct
9 Correct 389 ms 78712 KB Output is correct
10 Correct 239 ms 78576 KB Output is correct
11 Correct 208 ms 78712 KB Output is correct
12 Correct 289 ms 78704 KB Output is correct
13 Correct 423 ms 78840 KB Output is correct
14 Correct 238 ms 79096 KB Output is correct
15 Correct 316 ms 78708 KB Output is correct
16 Correct 333 ms 78668 KB Output is correct
17 Correct 279 ms 78584 KB Output is correct
18 Correct 368 ms 78584 KB Output is correct
19 Correct 118 ms 78584 KB Output is correct
20 Correct 376 ms 78716 KB Output is correct
21 Correct 233 ms 79224 KB Output is correct
22 Correct 383 ms 78712 KB Output is correct
23 Correct 176 ms 78832 KB Output is correct
24 Correct 144 ms 78904 KB Output is correct
25 Correct 248 ms 78940 KB Output is correct
26 Correct 220 ms 78840 KB Output is correct
27 Correct 486 ms 78712 KB Output is correct
28 Correct 139 ms 78840 KB Output is correct
29 Correct 359 ms 78716 KB Output is correct
30 Correct 375 ms 78812 KB Output is correct
31 Correct 191 ms 78844 KB Output is correct
32 Correct 240 ms 78832 KB Output is correct
33 Correct 147 ms 78840 KB Output is correct
34 Correct 317 ms 78676 KB Output is correct
35 Correct 162 ms 78848 KB Output is correct
36 Correct 368 ms 78844 KB Output is correct
37 Correct 188 ms 78840 KB Output is correct
38 Correct 314 ms 78936 KB Output is correct
39 Correct 171 ms 78844 KB Output is correct
40 Correct 254 ms 78896 KB Output is correct
41 Correct 242 ms 78712 KB Output is correct
42 Correct 327 ms 78972 KB Output is correct