oj.uz

Submission #140622

# Submission time Handle Problem Language Result Execution time Memory
140622 2019-08-03T19:41:58 Z CaroLinda Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 372 ms 262148 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 276 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 236 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 279 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 341 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 270 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 330 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 313 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 231 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 267 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 236 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 329 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 333 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 321 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 249 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 355 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 248 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 251 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 238 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 335 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 269 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 335 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 284 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 243 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 372 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 295 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 248 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 251 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 367 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 296 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 240 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 260 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 249 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 287 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 300 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 250 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 314 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 291 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 249 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 343 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 369 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 310 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 241 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 254 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)