oj.uz

Submission #140627

# Submission time Handle Problem Language Result Execution time Memory
140627 2019-08-03T19:56:26 Z CaroLinda Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 831 ms 157716 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 = 2e7+5 ;

using namespace std;

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

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


    sort(prime, prime+n) ;

    lp(i,0,n)
        for(int j = prime[i] ; j < MAX ; j += prime[i] )
           myMod[j-1] = max( myMod[j-1] , prime[i] - 1 ) ;

    for(int i = MAX ; i > 0 ; i-- )
        myMod[i] = max( myMod[i] , myMod[i+1] - 1 ) ;

    for(int i = 1 ; i <= MAX ; i++ )
    {
        dp[i] = MAX ;

        dp[i] = min( dp[i-myMod[i]] + 1 , dp[i] ) ;

    }

    lp(i,0,q)
    {
        int a ;
        scanf("%d", &a ) ;
        if(dp[a] >= MAX) printf("oo\n") ;
        else printf("%d\n" , dp[a]) ;
    }


}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:21: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:22: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:45:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a ) ;
         ~~~~~^~~~~~~~~~~
brunhilda.cpp:38:15: warning: iteration 20000004 invokes undefined behavior [-Waggressive-loop-optimizations]
         dp[i] = min( dp[i-myMod[i]] + 1 , dp[i] ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:34:23: note: within this loop
     for(int i = 1 ; i <= MAX ; i++ )
                     ~~^~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 156872 KB Output is correct
2 Correct 332 ms 156872 KB Output is correct
3 Correct 316 ms 156912 KB Output is correct
4 Correct 276 ms 156868 KB Output is correct
5 Correct 302 ms 156892 KB Output is correct
6 Correct 274 ms 156920 KB Output is correct
7 Correct 301 ms 156812 KB Output is correct
8 Correct 307 ms 156792 KB Output is correct
9 Correct 349 ms 156864 KB Output is correct
10 Correct 397 ms 156868 KB Output is correct
11 Correct 379 ms 156924 KB Output is correct
12 Correct 274 ms 156920 KB Output is correct
13 Correct 622 ms 156920 KB Output is correct
14 Correct 623 ms 156824 KB Output is correct
15 Correct 344 ms 157104 KB Output is correct
16 Correct 322 ms 156920 KB Output is correct
17 Correct 325 ms 156852 KB Output is correct
18 Correct 279 ms 156920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 156860 KB Output is correct
2 Correct 338 ms 157208 KB Output is correct
3 Correct 744 ms 157176 KB Output is correct
4 Correct 362 ms 156920 KB Output is correct
5 Correct 533 ms 157176 KB Output is correct
6 Correct 326 ms 156856 KB Output is correct
7 Correct 322 ms 156916 KB Output is correct
8 Correct 417 ms 156920 KB Output is correct
9 Correct 731 ms 157144 KB Output is correct
10 Correct 773 ms 157180 KB Output is correct
11 Correct 734 ms 157048 KB Output is correct
12 Correct 447 ms 156920 KB Output is correct
13 Correct 296 ms 156832 KB Output is correct
14 Correct 362 ms 157008 KB Output is correct
15 Correct 635 ms 157048 KB Output is correct
16 Correct 346 ms 157304 KB Output is correct
17 Correct 649 ms 156868 KB Output is correct
18 Correct 626 ms 157344 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 157316 KB Output is correct
2 Correct 759 ms 157132 KB Output is correct
3 Correct 763 ms 157276 KB Output is correct
4 Correct 491 ms 157324 KB Output is correct
5 Correct 386 ms 157428 KB Output is correct
6 Correct 641 ms 157304 KB Output is correct
7 Correct 563 ms 157432 KB Output is correct
8 Correct 634 ms 157244 KB Output is correct
9 Correct 652 ms 157304 KB Output is correct
10 Correct 528 ms 157056 KB Output is correct
11 Correct 458 ms 157048 KB Output is correct
12 Correct 591 ms 157004 KB Output is correct
13 Correct 716 ms 157364 KB Output is correct
14 Correct 441 ms 157444 KB Output is correct
15 Correct 619 ms 156996 KB Output is correct
16 Correct 691 ms 157132 KB Output is correct
17 Correct 601 ms 157032 KB Output is correct
18 Correct 772 ms 157192 KB Output is correct
19 Correct 310 ms 156920 KB Output is correct
20 Correct 771 ms 157448 KB Output is correct
21 Correct 501 ms 157592 KB Output is correct
22 Correct 778 ms 157560 KB Output is correct
23 Correct 401 ms 157176 KB Output is correct
24 Correct 337 ms 157252 KB Output is correct
25 Correct 538 ms 157176 KB Output is correct
26 Correct 492 ms 157132 KB Output is correct
27 Correct 831 ms 157432 KB Output is correct
28 Correct 336 ms 157152 KB Output is correct
29 Correct 730 ms 157560 KB Output is correct
30 Correct 679 ms 157412 KB Output is correct
31 Correct 430 ms 157176 KB Output is correct
32 Correct 419 ms 157152 KB Output is correct
33 Correct 306 ms 157152 KB Output is correct
34 Correct 563 ms 157368 KB Output is correct
35 Correct 351 ms 157120 KB Output is correct
36 Correct 752 ms 157472 KB Output is correct
37 Correct 398 ms 157716 KB Output is correct
38 Correct 675 ms 157176 KB Output is correct
39 Correct 360 ms 157180 KB Output is correct
40 Correct 612 ms 157148 KB Output is correct
41 Correct 498 ms 157364 KB Output is correct
42 Correct 780 ms 157304 KB Output is correct