oj.uz

Submission #140625

# Submission time Handle Problem Language Result Execution time Memory
140625 2019-08-03T19:52:43 Z CaroLinda Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 419 ms 80860 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++ )
    {
        if(myMod[i] == 0 ) dp[i] = MAX ;

        dp[i] = dp[i-myMod[i]] + 1 ;

    }

    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] = dp[i-myMod[i]] + 1 ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
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 136 ms 78584 KB Output is correct
2 Correct 155 ms 78584 KB Output is correct
3 Correct 145 ms 78584 KB Output is correct
4 Correct 134 ms 78712 KB Output is correct
5 Correct 142 ms 78556 KB Output is correct
6 Correct 135 ms 78632 KB Output is correct
7 Correct 143 ms 78720 KB Output is correct
8 Correct 154 ms 78604 KB Output is correct
9 Correct 169 ms 78600 KB Output is correct
10 Correct 185 ms 78584 KB Output is correct
11 Correct 178 ms 78712 KB Output is correct
12 Correct 133 ms 78668 KB Output is correct
13 Correct 276 ms 78608 KB Output is correct
14 Correct 283 ms 78604 KB Output is correct
15 Correct 166 ms 78620 KB Output is correct
16 Correct 179 ms 78556 KB Output is correct
17 Correct 162 ms 78692 KB Output is correct
18 Correct 146 ms 78796 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 78736 KB Output is correct
2 Correct 167 ms 79644 KB Output is correct
3 Correct 330 ms 79464 KB Output is correct
4 Correct 170 ms 78708 KB Output is correct
5 Correct 244 ms 79096 KB Output is correct
6 Correct 154 ms 78620 KB Output is correct
7 Correct 151 ms 78660 KB Output is correct
8 Correct 169 ms 78708 KB Output is correct
9 Correct 283 ms 79376 KB Output is correct
10 Correct 341 ms 79324 KB Output is correct
11 Incorrect 325 ms 79068 KB Output isn't correct
12 Correct 206 ms 78584 KB Output is correct
13 Correct 140 ms 78588 KB Output is correct
14 Correct 182 ms 78616 KB Output is correct
15 Correct 277 ms 79096 KB Output is correct
16 Correct 164 ms 79736 KB Output is correct
17 Correct 280 ms 78712 KB Output is correct
18 Correct 279 ms 79736 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 79480 KB Output is correct
2 Correct 336 ms 79412 KB Output is correct
3 Correct 340 ms 79752 KB Output is correct
4 Incorrect 243 ms 79580 KB Output isn't correct
5 Incorrect 204 ms 80860 KB Output isn't correct
6 Correct 303 ms 79596 KB Output is correct
7 Correct 264 ms 80248 KB Output is correct
8 Correct 293 ms 79572 KB Output is correct
9 Correct 293 ms 79544 KB Output is correct
10 Correct 237 ms 78724 KB Output is correct
11 Incorrect 215 ms 78840 KB Output isn't correct
12 Correct 274 ms 78912 KB Output is correct
13 Correct 337 ms 79972 KB Output is correct
14 Correct 220 ms 79992 KB Output is correct
15 Incorrect 282 ms 78976 KB Output isn't correct
16 Correct 347 ms 79068 KB Output is correct
17 Correct 277 ms 79224 KB Output is correct
18 Correct 345 ms 79584 KB Output is correct
19 Incorrect 153 ms 78864 KB Output isn't correct
20 Correct 347 ms 79676 KB Output is correct
21 Incorrect 256 ms 79992 KB Output isn't correct
22 Correct 378 ms 80760 KB Output is correct
23 Correct 204 ms 79864 KB Output is correct
24 Correct 181 ms 79756 KB Output is correct
25 Correct 281 ms 79736 KB Output is correct
26 Incorrect 246 ms 79608 KB Output isn't correct
27 Correct 419 ms 80248 KB Output is correct
28 Incorrect 180 ms 79736 KB Output isn't correct
29 Correct 376 ms 80632 KB Output is correct
30 Correct 322 ms 80504 KB Output is correct
31 Correct 196 ms 79608 KB Output is correct
32 Incorrect 213 ms 79608 KB Output isn't correct
33 Incorrect 167 ms 79580 KB Output isn't correct
34 Correct 270 ms 80248 KB Output is correct
35 Incorrect 183 ms 79672 KB Output isn't correct
36 Correct 403 ms 80632 KB Output is correct
37 Incorrect 203 ms 80760 KB Output isn't correct
38 Correct 299 ms 79604 KB Output is correct
39 Incorrect 197 ms 79736 KB Output isn't correct
40 Correct 272 ms 79736 KB Output is correct
41 Correct 240 ms 80288 KB Output is correct
42 Correct 319 ms 79888 KB Output is correct