oj.uz

Submission #31857

# Submission time Handle Problem Language Result Execution time Memory
31857 2017-09-11T07:46:03 Z minhtung0404 Brunhilda’s Birthday (BOI13_brunhilda) C++14
58.5714 / 100
 789 ms 80532 KB 
#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int M = 1e7 + 5;
const int inf = 1e9;
using namespace std;

int n, q, p[N], m, prime[M], ans[M], cnt = 1, ct;

int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 1; i <= n; i++){
        int z = p[i];
        for (int j = 0; j < M; j+=z) prime[j] = max(prime[j], z);
    }
    for (int i = 1; i < M; i++) ans[i] = -inf;
    while(ct < M){
        while(cnt < ct + prime[ct] && cnt < M) ans[cnt] = ans[ct] + 1, cnt++;
        ct++;
    }
    while(q--){
        cin >> m;
        if (ans[m] <= 0) cout << "oo\n";
        else cout << ans[m] << "\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 80532 KB Output is correct
2 Correct 69 ms 80532 KB Output is correct
3 Correct 86 ms 80532 KB Output is correct
4 Correct 66 ms 80532 KB Output is correct
5 Correct 46 ms 80532 KB Output is correct
6 Correct 89 ms 80532 KB Output is correct
7 Correct 79 ms 80532 KB Output is correct
8 Correct 86 ms 80532 KB Output is correct
9 Correct 96 ms 80532 KB Output is correct
10 Correct 123 ms 80532 KB Output is correct
11 Correct 119 ms 80532 KB Output is correct
12 Correct 46 ms 80532 KB Output is correct
13 Correct 253 ms 80532 KB Output is correct
14 Correct 279 ms 80532 KB Output is correct
15 Correct 116 ms 80532 KB Output is correct
16 Correct 89 ms 80532 KB Output is correct
17 Correct 96 ms 80532 KB Output is correct
18 Correct 113 ms 80532 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 80532 KB Output is correct
2 Correct 133 ms 80532 KB Output is correct
3 Correct 393 ms 80532 KB Output is correct
4 Correct 103 ms 80532 KB Output is correct
5 Correct 253 ms 80532 KB Output is correct
6 Correct 56 ms 80532 KB Output is correct
7 Correct 83 ms 80532 KB Output is correct
8 Correct 123 ms 80532 KB Output is correct
9 Correct 299 ms 80532 KB Output is correct
10 Correct 383 ms 80532 KB Output is correct
11 Correct 329 ms 80532 KB Output is correct
12 Correct 176 ms 80532 KB Output is correct
13 Correct 66 ms 80532 KB Output is correct
14 Correct 106 ms 80532 KB Output is correct
15 Correct 289 ms 80532 KB Output is correct
16 Correct 136 ms 80532 KB Output is correct
17 Correct 316 ms 80532 KB Output is correct
18 Correct 283 ms 80532 KB Output is correct

Subtask #3
18.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 80532 KB Output is correct
2 Correct 523 ms 80532 KB Output is correct
3 Runtime error 493 ms 80532 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 323 ms 80532 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 293 ms 80532 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 526 ms 80532 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 453 ms 80532 KB Execution timed out (wall clock limit exceeded)
8 Correct 376 ms 80532 KB Output is correct
9 Runtime error 516 ms 80532 KB Execution timed out (wall clock limit exceeded)
10 Correct 319 ms 80532 KB Output is correct
11 Correct 186 ms 80532 KB Output is correct
12 Correct 269 ms 80532 KB Output is correct
13 Runtime error 573 ms 80532 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 303 ms 80532 KB Execution timed out (wall clock limit exceeded)
15 Correct 386 ms 80532 KB Output is correct
16 Correct 346 ms 80532 KB Output is correct
17 Correct 336 ms 80532 KB Output is correct
18 Correct 466 ms 80532 KB Output is correct
19 Correct 143 ms 80532 KB Output is correct
20 Runtime error 529 ms 80532 KB Execution timed out (wall clock limit exceeded)
21 Runtime error 353 ms 80532 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 556 ms 80532 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 283 ms 80532 KB Execution timed out (wall clock limit exceeded)
24 Correct 266 ms 80532 KB Output is correct
25 Runtime error 339 ms 80532 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 323 ms 80532 KB Execution timed out (wall clock limit exceeded)
27 Runtime error 789 ms 80532 KB Execution timed out (wall clock limit exceeded)
28 Runtime error 233 ms 80532 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 506 ms 80532 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 539 ms 80532 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 256 ms 80532 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 306 ms 80532 KB Execution timed out (wall clock limit exceeded)
33 Runtime error 193 ms 80532 KB Execution timed out (wall clock limit exceeded)
34 Correct 429 ms 80532 KB Output is correct
35 Runtime error 236 ms 80532 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 546 ms 80532 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 303 ms 80532 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 436 ms 80532 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 253 ms 80532 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 386 ms 80532 KB Execution timed out (wall clock limit exceeded)
41 Runtime error 379 ms 80532 KB Execution timed out (wall clock limit exceeded)
42 Runtime error 536 ms 80532 KB Execution timed out (wall clock limit exceeded)