oj.uz

Submission #140626

# Submission time Handle Problem Language Result Execution time Memory
140626 2019-08-03T19:55:50 Z CaroLinda Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 439 ms 79352 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] , 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 10000004 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 139 ms 78644 KB Output is correct
2 Correct 166 ms 78592 KB Output is correct
3 Correct 161 ms 78584 KB Output is correct
4 Correct 137 ms 78584 KB Output is correct
5 Correct 147 ms 78584 KB Output is correct
6 Correct 136 ms 78716 KB Output is correct
7 Correct 146 ms 78620 KB Output is correct
8 Correct 151 ms 78588 KB Output is correct
9 Correct 171 ms 78584 KB Output is correct
10 Correct 186 ms 78556 KB Output is correct
11 Correct 181 ms 78584 KB Output is correct
12 Correct 135 ms 78584 KB Output is correct
13 Correct 281 ms 78592 KB Output is correct
14 Correct 274 ms 78660 KB Output is correct
15 Correct 161 ms 78584 KB Output is correct
16 Correct 154 ms 78584 KB Output is correct
17 Correct 169 ms 78604 KB Output is correct
18 Correct 138 ms 78552 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 78584 KB Output is correct
2 Correct 172 ms 78940 KB Output is correct
3 Correct 331 ms 78860 KB Output is correct
4 Correct 171 ms 78584 KB Output is correct
5 Correct 240 ms 78748 KB Output is correct
6 Correct 158 ms 78576 KB Output is correct
7 Correct 162 ms 78628 KB Output is correct
8 Correct 169 ms 78584 KB Output is correct
9 Correct 286 ms 78824 KB Output is correct
10 Correct 321 ms 78968 KB Output is correct
11 Incorrect 329 ms 78844 KB Output isn't correct
12 Correct 205 ms 78716 KB Output is correct
13 Correct 142 ms 78584 KB Output is correct
14 Correct 172 ms 78584 KB Output is correct
15 Correct 277 ms 78812 KB Output is correct
16 Correct 168 ms 79044 KB Output is correct
17 Correct 300 ms 78568 KB Output is correct
18 Correct 281 ms 78968 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 79004 KB Output is correct
2 Correct 347 ms 78812 KB Output is correct
3 Correct 366 ms 78968 KB Output is correct
4 Incorrect 285 ms 78968 KB Output isn't correct
5 Incorrect 208 ms 79224 KB Output isn't correct
6 Correct 312 ms 79096 KB Output is correct
7 Correct 280 ms 79100 KB Output is correct
8 Correct 285 ms 78840 KB Output is correct
9 Correct 300 ms 78908 KB Output is correct
10 Correct 242 ms 78748 KB Output is correct
11 Incorrect 235 ms 78712 KB Output isn't correct
12 Correct 273 ms 78840 KB Output is correct
13 Correct 336 ms 78968 KB Output is correct
14 Correct 222 ms 79100 KB Output is correct
15 Incorrect 328 ms 78720 KB Output isn't correct
16 Correct 317 ms 78712 KB Output is correct
17 Correct 285 ms 78840 KB Output is correct
18 Correct 340 ms 78840 KB Output is correct
19 Incorrect 157 ms 78768 KB Output isn't correct
20 Correct 355 ms 78992 KB Output is correct
21 Incorrect 256 ms 79224 KB Output isn't correct
22 Correct 366 ms 79284 KB Output is correct
23 Correct 205 ms 78968 KB Output is correct
24 Correct 184 ms 78932 KB Output is correct
25 Correct 267 ms 78944 KB Output is correct
26 Incorrect 250 ms 78840 KB Output isn't correct
27 Correct 385 ms 79060 KB Output is correct
28 Incorrect 197 ms 78968 KB Output isn't correct
29 Correct 355 ms 79200 KB Output is correct
30 Correct 325 ms 79224 KB Output is correct
31 Correct 199 ms 78968 KB Output is correct
32 Incorrect 212 ms 78892 KB Output isn't correct
33 Incorrect 190 ms 78968 KB Output isn't correct
34 Correct 270 ms 79056 KB Output is correct
35 Incorrect 188 ms 78968 KB Output isn't correct
36 Correct 439 ms 79196 KB Output is correct
37 Incorrect 204 ms 79352 KB Output isn't correct
38 Correct 323 ms 78940 KB Output is correct
39 Incorrect 220 ms 78968 KB Output isn't correct
40 Correct 277 ms 78848 KB Output is correct
41 Correct 249 ms 79096 KB Output is correct
42 Correct 325 ms 78944 KB Output is correct