oj.uz

답안 #26991

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26991 2017-07-08T09:44:50 Z zoomswk Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 0 ms 1844 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)