oj.uz

Submission #31893

# Submission time Handle Problem Language Result Execution time Memory
31893 2017-09-12T14:34:30 Z chonka Brunhilda’s Birthday (BOI13_brunhilda) C++
0 / 100
 0 ms 1844 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std ;

#define MAXN 100007

int n  , m ;
int a[ MAXN ] ;
int b[ MAXN ] ;
vector < int > v[ 100 * MAXN ] ;
int ans[ 100 * MAXN ] ;
int akt[ MAXN ] ;
int lim ;

void input ( ) {
    scanf ( "%d%d" , &n , &m ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    lim = 1 ;
    int i , j ;
    for ( i = 1 ; i <= 7 ; i ++ ) {
        lim *= 10 ;
    }
    deque < pair < int , int > > q ;
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = a[ i ] ; j <= lim ; j += a[ i ] ) {
            v[ j ].push_back ( i ) ;
        }
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        q.push_front ( make_pair ( 0 , i ) ) ;
        akt[ i ] = 0 ;
    }
    for ( i = 1 ; i <= lim ; i ++ ) {
        int sz = v[ i ].size ( ) ;
        for ( j = 0 ; j < sz ; j ++ ) {
            akt[ v[ i ][ j ] ] += a[ v[ i ][ j ] ] ;
            q.push_front ( make_pair ( akt[ v[ i ][ j ] ] , v[ i ][ j ] ) ) ;
        }
        while ( q.empty ( ) == false ) {
            pair < int , int > p = q.back ( ) ;
            if ( akt[ p.second ] != p.first ) { q.pop_back ( ) ; }
            else { break ; }
        }
        ans[ i ] = ans[ (q.back()).first ] + 1 ;
        if ( ans[ q.back().first ] == -1 || (q.back()).first == i ) { ans[ i ] = -1 ; }
    }
    while ( m != 0 ) {
        m -- ;
        int x ;
        scanf ( "%d" , &x ) ;
        if ( ans[ x ] != -1 ) {
            printf ( "%d\n" , ans[ x ] ) ;
        }
        else {
            printf ( "oo\n" ) ;
        }
    }

}


int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message

brunhilda.cpp: In function 'void input()':
brunhilda.cpp:18:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &m ) ;
                                ^
brunhilda.cpp:21:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^
brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:58:29: 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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)