oj.uz

Submission #399272

# Submission time Handle Problem Language Result Execution time Memory
399272 2021-05-05T13:51:54 Z cpp219 Brunhilda’s Birthday (BOI13_brunhilda) C++14
80.3175 / 100
 380 ms 158532 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e7 + 9;
const ll inf = 1e15 + 7;

ll n,Q,dp[N],jump[N],x;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++){
        cin>>x;
        for (ll j = x - 1;j < N;j += x) jump[j] = x - 1;
    }
    for (ll i = N - 3;i >= 1;i--){
        dp[i] = inf;
        jump[i] = max(jump[i],jump[i + 1] - 1);
    }
    dp[0] = 0;
    for (ll i = 1;i < N;i++){
        ll nxt = max(0ll,i - jump[i]);
        dp[i] = min(dp[i],dp[nxt] + 1);
    }
    while(Q--){
        cin>>x;
        if (dp[x] == inf) cout<<"oo";
        else cout<<dp[x]; cout<<"\n";
    }
}

Compilation message

brunhilda.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
brunhilda.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
brunhilda.cpp: In function 'int main()':
brunhilda.cpp:41:9: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
   41 |         else cout<<dp[x]; cout<<"\n";
      |         ^~~~
brunhilda.cpp:41:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
   41 |         else cout<<dp[x]; cout<<"\n";
      |                           ^~~~
brunhilda.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   21 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 156868 KB Output is correct
2 Correct 160 ms 156800 KB Output is correct
3 Correct 151 ms 156744 KB Output is correct
4 Correct 137 ms 156868 KB Output is correct
5 Correct 153 ms 156856 KB Output is correct
6 Correct 137 ms 156816 KB Output is correct
7 Correct 150 ms 156740 KB Output is correct
8 Correct 159 ms 156812 KB Output is correct
9 Correct 179 ms 156924 KB Output is correct
10 Correct 201 ms 156764 KB Output is correct
11 Correct 192 ms 156868 KB Output is correct
12 Correct 138 ms 156844 KB Output is correct
13 Correct 293 ms 156868 KB Output is correct
14 Correct 293 ms 156852 KB Output is correct
15 Correct 170 ms 156744 KB Output is correct
16 Correct 160 ms 156856 KB Output is correct
17 Correct 157 ms 156868 KB Output is correct
18 Correct 135 ms 156824 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 156980 KB Output is correct
2 Correct 169 ms 157544 KB Output is correct
3 Correct 337 ms 157252 KB Output is correct
4 Correct 167 ms 156828 KB Output is correct
5 Correct 251 ms 157248 KB Output is correct
6 Correct 151 ms 156816 KB Output is correct
7 Correct 151 ms 156816 KB Output is correct
8 Correct 165 ms 156764 KB Output is correct
9 Correct 288 ms 157508 KB Output is correct
10 Correct 345 ms 157312 KB Output is correct
11 Incorrect 328 ms 157124 KB Output isn't correct
12 Correct 208 ms 156808 KB Output is correct
13 Correct 142 ms 156864 KB Output is correct
14 Correct 168 ms 156848 KB Output is correct
15 Correct 287 ms 157116 KB Output is correct
16 Correct 166 ms 157624 KB Output is correct
17 Correct 293 ms 156788 KB Output is correct
18 Correct 285 ms 157516 KB Output is correct

Subtask #3
41.4285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 157508 KB Output is correct
2 Correct 348 ms 157452 KB Output is correct
3 Correct 350 ms 157764 KB Output is correct
4 Incorrect 243 ms 157888 KB Output isn't correct
5 Incorrect 203 ms 158472 KB Output isn't correct
6 Correct 308 ms 157844 KB Output is correct
7 Correct 263 ms 158020 KB Output is correct
8 Correct 299 ms 157596 KB Output is correct
9 Correct 306 ms 157504 KB Output is correct
10 Correct 237 ms 156992 KB Output is correct
11 Incorrect 208 ms 157124 KB Output isn't correct
12 Correct 275 ms 157160 KB Output is correct
13 Correct 338 ms 157952 KB Output is correct
14 Correct 231 ms 158132 KB Output is correct
15 Incorrect 287 ms 157128 KB Output isn't correct
16 Correct 310 ms 157088 KB Output is correct
17 Correct 276 ms 157248 KB Output is correct
18 Correct 349 ms 157352 KB Output is correct
19 Incorrect 153 ms 157144 KB Output isn't correct
20 Correct 349 ms 157704 KB Output is correct
21 Incorrect 256 ms 158180 KB Output isn't correct
22 Correct 370 ms 158532 KB Output is correct
23 Correct 199 ms 158020 KB Output is correct
24 Correct 176 ms 157844 KB Output is correct
25 Correct 261 ms 157892 KB Output is correct
26 Incorrect 242 ms 157704 KB Output isn't correct
27 Correct 380 ms 158020 KB Output is correct
28 Incorrect 171 ms 157868 KB Output isn't correct
29 Correct 343 ms 158464 KB Output is correct
30 Correct 316 ms 158228 KB Output is correct
31 Correct 191 ms 157660 KB Output is correct
32 Incorrect 210 ms 157872 KB Output isn't correct
33 Incorrect 163 ms 157736 KB Output isn't correct
34 Correct 264 ms 158016 KB Output is correct
35 Incorrect 178 ms 158020 KB Output isn't correct
36 Correct 360 ms 158380 KB Output is correct
37 Incorrect 200 ms 158532 KB Output isn't correct
38 Correct 308 ms 157872 KB Output is correct
39 Incorrect 183 ms 157892 KB Output isn't correct
40 Correct 268 ms 157844 KB Output is correct
41 Correct 240 ms 158016 KB Output is correct
42 Correct 326 ms 157960 KB Output is correct