oj.uz

Submission #26993

# Submission time Handle Problem Language Result Execution time Memory
26993 2017-07-08T09:49:47 Z zoomswk Brunhilda’s Birthday (BOI13_brunhilda) C++14
17.7778 / 100
 1000 ms 178152 KB 
#include <bits/stdc++.h>
using namespace std;

int m;
vector<int> di[3000005];
int p[100005];
int t[200005];
int dp[3000005];

int qr(int l, int r){
    int res = 1e9;
    for(l+=m, r+=m; l<r; l>>=1, r>>=1){
        if(l&1) res = min(res, t[l++]);
        if(r&1) res = min(res, t[--r]);
    }
    return res;
}

void upd(int idx, int v){
    for(t[idx+=m]=v; idx>1; idx>>=1) t[idx>>1] = min(t[idx], t[idx^1]);
    return;
}

int main(){
    int Q;
    scanf("%d%d", &m, &Q);
    for(int i=1; i<=m; i++){
        scanf("%d", &p[i]);
        for(int j=p[i]; j<=(int)(3e6); j+=p[i]) di[j].push_back(i);
    }
    for(int i=1; i<=(int)(3e6); i++){
        for(int x : di[i]) upd(x, 1e9);
        dp[i] = qr(1, m+1) + 1;
        for(int x : di[i]) upd(x, dp[i]);
    }
    while(Q--){
        int x;
        scanf("%d", &x);
        if(dp[x] <= 1e7) printf("%d\n", dp[x]);
        else printf("oo\n");
    }
    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:26:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &Q);
                          ^
brunhilda.cpp:28:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
                           ^
brunhilda.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 101064 KB Output is correct
2 Correct 443 ms 153336 KB Output is correct
3 Correct 243 ms 143832 KB Output is correct
4 Correct 116 ms 92220 KB Output is correct
5 Correct 173 ms 109908 KB Output is correct
6 Correct 113 ms 101064 KB Output is correct
7 Correct 233 ms 143832 KB Output is correct
8 Correct 353 ms 155712 KB Output is correct
9 Correct 523 ms 162312 KB Output is correct
10 Correct 629 ms 164952 KB Output is correct
11 Correct 479 ms 150960 KB Output is correct
12 Correct 123 ms 90372 KB Output is correct
13 Execution timed out 1000 ms 174588 KB Execution timed out
14 Execution timed out 1000 ms 174456 KB Execution timed out
15 Correct 463 ms 151356 KB Output is correct
16 Correct 443 ms 153336 KB Output is correct
17 Correct 369 ms 109644 KB Output is correct
18 Correct 139 ms 92220 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 101064 KB Output isn't correct
2 Incorrect 393 ms 105420 KB Output isn't correct
3 Execution timed out 1000 ms 176700 KB Execution timed out
4 Incorrect 633 ms 123768 KB Output isn't correct
5 Execution timed out 1000 ms 161916 KB Execution timed out
6 Incorrect 456 ms 141588 KB Output isn't correct
7 Incorrect 326 ms 101064 KB Output isn't correct
8 Incorrect 499 ms 119412 KB Output isn't correct
9 Execution timed out 1000 ms 167724 KB Execution timed out
10 Execution timed out 1000 ms 176700 KB Execution timed out
11 Execution timed out 1000 ms 175116 KB Execution timed out
12 Incorrect 999 ms 156900 KB Output isn't correct
13 Incorrect 283 ms 108192 KB Output isn't correct
14 Incorrect 646 ms 123768 KB Output isn't correct
15 Execution timed out 1000 ms 171948 KB Execution timed out
16 Incorrect 419 ms 105420 KB Output isn't correct
17 Execution timed out 1000 ms 172740 KB Execution timed out
18 Execution timed out 1000 ms 169704 KB Execution timed out

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 173400 KB Execution timed out
2 Execution timed out 1000 ms 175776 KB Execution timed out
3 Execution timed out 1000 ms 176172 KB Execution timed out
4 Execution timed out 1000 ms 159804 KB Execution timed out
5 Incorrect 459 ms 106344 KB Output isn't correct
6 Execution timed out 1000 ms 168648 KB Execution timed out
7 Execution timed out 1000 ms 153732 KB Execution timed out
8 Execution timed out 1000 ms 173400 KB Execution timed out
9 Execution timed out 1000 ms 173400 KB Execution timed out
10 Execution timed out 1000 ms 151620 KB Execution timed out
11 Execution timed out 1000 ms 141588 KB Execution timed out
12 Execution timed out 1000 ms 168120 KB Execution timed out
13 Execution timed out 1000 ms 172080 KB Execution timed out
14 Incorrect 823 ms 166800 KB Output isn't correct
15 Execution timed out 1000 ms 173136 KB Execution timed out
16 Execution timed out 1000 ms 174324 KB Execution timed out
17 Execution timed out 1000 ms 164820 KB Execution timed out
18 Execution timed out 1000 ms 175776 KB Execution timed out
19 Incorrect 419 ms 124560 KB Output isn't correct
20 Execution timed out 1000 ms 176172 KB Execution timed out
21 Execution timed out 1000 ms 171024 KB Execution timed out
22 Execution timed out 1000 ms 176700 KB Execution timed out
23 Incorrect 569 ms 111096 KB Output isn't correct
24 Incorrect 306 ms 102516 KB Output isn't correct
25 Execution timed out 1000 ms 156900 KB Execution timed out
26 Execution timed out 1000 ms 159804 KB Execution timed out
27 Execution timed out 1000 ms 178152 KB Execution timed out
28 Incorrect 443 ms 118356 KB Output isn't correct
29 Execution timed out 1000 ms 171024 KB Execution timed out
30 Execution timed out 1000 ms 167196 KB Execution timed out
31 Incorrect 583 ms 121260 KB Output isn't correct
32 Incorrect 793 ms 130368 KB Output isn't correct
33 Incorrect 249 ms 95256 KB Output isn't correct
34 Execution timed out 1000 ms 153732 KB Execution timed out
35 Incorrect 516 ms 120204 KB Output isn't correct
36 Execution timed out 1000 ms 176304 KB Execution timed out
37 Incorrect 533 ms 106344 KB Output isn't correct
38 Execution timed out 1000 ms 168648 KB Execution timed out
39 Incorrect 479 ms 107532 KB Output isn't correct
40 Execution timed out 1000 ms 164424 KB Execution timed out
41 Execution timed out 1000 ms 160596 KB Execution timed out
42 Execution timed out 1000 ms 174852 KB Execution timed out