Submission #140622

#	Time	Username	Problem	Language	Result	Execution time	Memory
140622		CaroLinda	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	0 / 100	372 ms	262148 KiB

brunhilda

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i=a;i<b;i++)
#define ff first
#define ss second
#define pii pair<int,int>
#define mk make_pair
#define pb push_back
#define ll long long

const int MAXN = 1e5+10;
const int MAX = 1e7+5 ;

using namespace std;

int n , q ;
int prime[MAXN] , minMod[MAX] , dp[MAX] ;

vector<int> fatPrime[MAX+5] ;

// -------------------------------

int minAcumulado = MAX ;
void findMinMod(int x)
{
    if( x == 0 ) return ;

    if( minAcumulado == x ) minMod[x] = -1 ;
    else minMod[x] = minAcumulado ;

    for(int i : fatPrime[x])
        minAcumulado = min( minAcumulado , (x-1) - (x-1)%i ) ;

    findMinMod(x-1) ;

}

int main()
{
    scanf("%d %d", &n , &q ) ;
    lp(i,0,n) scanf("%d" , &prime[i] ) ;


    sort(prime, prime+n) ;

    lp(i,0,n)
        for(ll k = 1 ; k * prime[i] < MAX ; k++ )
            fatPrime[ prime[i]*k ].pb(prime[i]) ;

    int idx = 0 ;

    lp(i,0, fatPrime[MAX].size() + 1 )
    {

        while( idx < n && (i == fatPrime[MAX].size() || prime[idx] < fatPrime[MAX][i]) )
            {  minAcumulado = min( minAcumulado , MAX - MAX%prime[idx++] ) ; }

        idx ++ ;

    }

    findMinMod(MAX) ;

    lp(i,1,MAX+1)
    {
        if( minMod[i] == -1 )
        {
            dp[i] = -1 ;
            continue ;
        }
        dp[i] = dp[minMod[i]] ;
        if(dp[i] != -1) dp[i] ++ ;
    }

    lp(i,0,q)
    {
        int a ;
        scanf("%d", &a ) ;

        if(dp[a] == -1) printf("oo\n") ;
        else printf("%d\n" , dp[a] ) ;

    }


}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:3:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i=a;i<b;i++)
brunhilda.cpp:52:8:
     lp(i,0, fatPrime[MAX].size() + 1 )
        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:52:5: note: in expansion of macro 'lp'
     lp(i,0, fatPrime[MAX].size() + 1 )
     ^~
brunhilda.cpp:55:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while( idx < n && (i == fatPrime[MAX].size() || prime[idx] < fatPrime[MAX][i]) )
                            ~~^~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n , &q ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     lp(i,0,n) scanf("%d" , &prime[i] ) ;
               ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a ) ;
         ~~~~~^~~~~~~~~~~
brunhilda.cpp:66:21: warning: iteration 10000004 invokes undefined behavior [-Waggressive-loop-optimizations]
         if( minMod[i] == -1 )
             ~~~~~~~~^
brunhilda.cpp:3:32: note: within this loop
 #define lp(i,a,b) for(int i=a;i<b;i++)
brunhilda.cpp:64:8:
     lp(i,1,MAX+1)
        ~~~~~~~~~                
brunhilda.cpp:64:5: note: in expansion of macro 'lp'
     lp(i,1,MAX+1)
     ^~

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