Submission #31893

#	Time	Username	Problem	Language	Result	Execution time	Memory
31893		chonka	Brunhilda’s Birthday (BOI13_brunhilda)	C++98	0 / 100	0 ms	1844 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 ] ;
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 (stderr)

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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60