oj.uz

Submission #399273

# Submission time Handle Problem Language Result Execution time Memory
399273 2021-05-05T13:53:31 Z cpp219 Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 480 ms 188776 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 = 12e6 + 9;
const ll inf = 1e9 + 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 162 ms 188072 KB Output is correct
2 Correct 187 ms 188060 KB Output is correct
3 Correct 184 ms 188100 KB Output is correct
4 Correct 178 ms 188176 KB Output is correct
5 Correct 182 ms 188092 KB Output is correct
6 Correct 167 ms 188164 KB Output is correct
7 Correct 189 ms 188056 KB Output is correct
8 Correct 199 ms 188100 KB Output is correct
9 Correct 218 ms 188088 KB Output is correct
10 Correct 247 ms 188060 KB Output is correct
11 Correct 252 ms 188060 KB Output is correct
12 Correct 163 ms 188156 KB Output is correct
13 Correct 356 ms 188112 KB Output is correct
14 Correct 358 ms 188184 KB Output is correct
15 Correct 205 ms 188052 KB Output is correct
16 Correct 196 ms 188228 KB Output is correct
17 Correct 193 ms 188088 KB Output is correct
18 Correct 163 ms 188160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 188100 KB Output is correct
2 Correct 205 ms 188064 KB Output is correct
3 Correct 430 ms 188052 KB Output is correct
4 Correct 221 ms 188052 KB Output is correct
5 Correct 302 ms 188076 KB Output is correct
6 Correct 194 ms 188100 KB Output is correct
7 Correct 184 ms 188172 KB Output is correct
8 Correct 201 ms 188100 KB Output is correct
9 Correct 350 ms 188144 KB Output is correct
10 Correct 423 ms 188168 KB Output is correct
11 Correct 398 ms 188056 KB Output is correct
12 Correct 251 ms 188100 KB Output is correct
13 Correct 167 ms 188088 KB Output is correct
14 Correct 202 ms 188124 KB Output is correct
15 Correct 348 ms 188064 KB Output is correct
16 Correct 198 ms 188152 KB Output is correct
17 Correct 354 ms 188096 KB Output is correct
18 Correct 348 ms 188128 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 188188 KB Output is correct
2 Correct 419 ms 188164 KB Output is correct
3 Correct 429 ms 188356 KB Output is correct
4 Correct 288 ms 188356 KB Output is correct
5 Correct 233 ms 188280 KB Output is correct
6 Correct 364 ms 188356 KB Output is correct
7 Correct 315 ms 188228 KB Output is correct
8 Correct 368 ms 188216 KB Output is correct
9 Correct 369 ms 188176 KB Output is correct
10 Correct 291 ms 188228 KB Output is correct
11 Correct 255 ms 188220 KB Output is correct
12 Correct 333 ms 188228 KB Output is correct
13 Correct 414 ms 188328 KB Output is correct
14 Correct 268 ms 188776 KB Output is correct
15 Correct 356 ms 188148 KB Output is correct
16 Correct 379 ms 188224 KB Output is correct
17 Correct 334 ms 188188 KB Output is correct
18 Correct 437 ms 188164 KB Output is correct
19 Correct 187 ms 188200 KB Output is correct
20 Correct 457 ms 188312 KB Output is correct
21 Correct 313 ms 188700 KB Output is correct
22 Correct 463 ms 188328 KB Output is correct
23 Correct 245 ms 188344 KB Output is correct
24 Correct 211 ms 188380 KB Output is correct
25 Correct 320 ms 188576 KB Output is correct
26 Correct 297 ms 188312 KB Output is correct
27 Correct 480 ms 188192 KB Output is correct
28 Correct 206 ms 188388 KB Output is correct
29 Correct 422 ms 188316 KB Output is correct
30 Correct 393 ms 188320 KB Output is correct
31 Correct 237 ms 188356 KB Output is correct
32 Correct 247 ms 188488 KB Output is correct
33 Correct 206 ms 188376 KB Output is correct
34 Correct 326 ms 188176 KB Output is correct
35 Correct 234 ms 188380 KB Output is correct
36 Correct 440 ms 188348 KB Output is correct
37 Correct 256 ms 188252 KB Output is correct
38 Correct 370 ms 188420 KB Output is correct
39 Correct 215 ms 188356 KB Output is correct
40 Correct 330 ms 188360 KB Output is correct
41 Correct 307 ms 188188 KB Output is correct
42 Correct 399 ms 188452 KB Output is correct