oj.uz

Submission #26992

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

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

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)(1e6); j+=p[i]) di[j].push_back(i);
    }
    for(int i=1; i<=(int)(1e6); 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 35816 KB Output is correct
2 Correct 153 ms 53240 KB Output is correct
3 Correct 79 ms 50072 KB Output is correct
4 Correct 39 ms 32912 KB Output is correct
5 Correct 53 ms 38852 KB Output is correct
6 Correct 46 ms 35816 KB Output is correct
7 Correct 83 ms 50072 KB Output is correct
8 Correct 153 ms 54032 KB Output is correct
9 Correct 156 ms 56276 KB Output is correct
10 Correct 243 ms 57068 KB Output is correct
11 Correct 173 ms 52448 KB Output is correct
12 Correct 46 ms 32252 KB Output is correct
13 Correct 526 ms 59972 KB Output is correct
14 Correct 533 ms 59972 KB Output is correct
15 Correct 159 ms 52580 KB Output is correct
16 Correct 166 ms 53240 KB Output is correct
17 Correct 113 ms 38720 KB Output is correct
18 Correct 76 ms 32912 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 96 ms 35816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 109 ms 37004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 716 ms 62084 KB Output isn't correct
4 Runtime error 149 ms 43604 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 446 ms 56540 KB Output isn't correct
6 Incorrect 163 ms 49280 KB Output isn't correct
7 Runtime error 89 ms 35816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 156 ms 42152 KB Output isn't correct
9 Incorrect 526 ms 58784 KB Output isn't correct
10 Incorrect 709 ms 62084 KB Output isn't correct
11 Runtime error 519 ms 61028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 289 ms 54560 KB Output isn't correct
13 Runtime error 79 ms 38192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 179 ms 43604 KB Output isn't correct
15 Incorrect 559 ms 60104 KB Output isn't correct
16 Runtime error 106 ms 37004 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 526 ms 59576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Incorrect 529 ms 59048 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 529 ms 60632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 639 ms 61424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 636 ms 61556 KB Output isn't correct
4 Runtime error 289 ms 55484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 106 ms 36872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 479 ms 58520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 423 ms 53240 KB Output isn't correct
8 Runtime error 476 ms 60632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 556 ms 60632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 349 ms 53372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 239 ms 49808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 449 ms 58256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Incorrect 636 ms 60236 KB Output isn't correct
14 Incorrect 276 ms 57728 KB Output isn't correct
15 Runtime error 516 ms 59708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 599 ms 60104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 493 ms 57992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 669 ms 61424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 79 ms 43736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 749 ms 61556 KB Output isn't correct
21 Runtime error 306 ms 59048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 643 ms 61820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 123 ms 38984 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 93 ms 36344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 309 ms 54692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 293 ms 55484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Incorrect 829 ms 62480 KB Output isn't correct
28 Runtime error 119 ms 41624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 503 ms 59972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 453 ms 59048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 136 ms 42680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 166 ms 45848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 46 ms 33836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Incorrect 403 ms 53240 KB Output isn't correct
35 Runtime error 123 ms 42284 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 593 ms 61556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 109 ms 36872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 449 ms 58520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 109 ms 38060 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 423 ms 57200 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Incorrect 389 ms 55484 KB Output isn't correct
42 Incorrect 666 ms 60104 KB Output isn't correct