Submission #31915

#	Time	Username	Problem	Language	Result	Execution time	Memory
31915		chonka	Brunhilda’s Birthday (BOI13_brunhilda)	C++98	100 / 100	479 ms	80928 KiB

brunhilda

#include<iostream>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std ;

#define MAXN 100007

int n  , m ;
int a[ MAXN ] ;
int b[ MAXN ] ;
int ans[ 100 * MAXN ] ;
int lim ;
int f[ 100 * MAXN ] ;

void input ( ) {
    scanf ( "%d%d" , &n , &m ) ;
    int i , j ;
    lim = 1 ;
    for ( i = 1 ; i <= 7 ; i ++ ) {
        lim *= 10 ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
        for ( j = 0 ; j <= lim ; j += a[ i ] ) {
            f[ j ] = a[ i ] ;
        }
    }
}

void solve ( ) {
    int i , j ;
    long long prod = 1 ;
    for ( i = n ; i >= 1 ; i -- ) {
        prod *= a[ i ] ;
        if ( prod > lim ) { prod = lim + 1 ; }
    }
    int lst = 0 ;
    for ( i = 1 ; i <= lim ; i ++ ) { ans[ i ] = -1 ; }
    for ( i = 1 ; i < prod ; i ++ ) {
        while ( f[ lst ] == 0 || lst + f[ lst ] <= i ) {
            lst ++ ;
        }
        if ( lst >= i ) { ans[ i ] = -1 ; }
        else { ans[ i ] = ans[ lst ] + 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 (stderr)

brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:32:13: warning: unused variable 'j' [-Wunused-variable]
     int i , j ;
             ^
brunhilda.cpp: In function 'void input()':
brunhilda.cpp:17: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:24: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:50:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &x ) ;
                             ^

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 60 / 60