oj.uz

Submission #447674

# Submission time Handle Problem Language Result Execution time Memory
447674 2021-07-27T10:06:55 Z NguyenDN Brunhilda’s Birthday (BOI13_brunhilda) C++14
100 / 100
 477 ms 189940 KB 
#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
*/
#define pb push_back
#define gcin(s) getline(cin,s)
#define el "\n"
#define sz(s) s.size()
#define fi first
#define sc second
#define testbit(n, bit) ((n>>bit) & 1)
#define flipbit(n, bit) (n ^ (1ll << bit))
#define reset(x, num) memset(x, num, sizeof(x))
#define all(x) x.begin(), x.end()
#define task "BIRTHDAY"
#define ll long long
#define ull unsigned long long
#define ld long double
using namespace std;
const ll maxe=12e6+10;
const ll maxf=1e3+1;
const ll oo=1e18;
const ll mod=1e9+7;
const ld Pi=atan(1.0L) * 4;
typedef ll mang[maxe];
typedef ll bang[maxf][maxf];
ll n, q;
mang jump, f;
int main () {
    ios_base:: sync_with_stdio(false);
    cout.tie(nullptr); cin.tie(nullptr);
    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++){
        ll x;
        cin >> x;
        for (ll j=x-1; j<maxe; j+=x) jump[j]=x-1;
    }
    for (ll i=maxe-3; i>=1; i--){
        f[i]=oo;
        jump[i]=max(jump[i],jump[i+1] - 1);
    }
    f[0]=0;
    for (ll i=1; i<maxe; i++){
        ll nxt=max(0ll, i-jump[i]);
        f[i]=min(f[i], f[nxt] + 1);
    }
    while(q--){
        ll x;
        cin >> x;
        if (f[x]==oo) cout << "oo" << el;
        else cout << f[x] << el;
    }
}

////////////////////////////////////////////////////////////////////////////////////////
//                                                                                    //
//                          Coded by Nguyen Duc Nam                                   //
//                                                                                    //
////////////////////////////////////////////////////////////////////////////////////////

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 188172 KB Output is correct
2 Correct 189 ms 188152 KB Output is correct
3 Correct 216 ms 188156 KB Output is correct
4 Correct 173 ms 188140 KB Output is correct
5 Correct 174 ms 188100 KB Output is correct
6 Correct 161 ms 188160 KB Output is correct
7 Correct 183 ms 188100 KB Output is correct
8 Correct 188 ms 188060 KB Output is correct
9 Correct 207 ms 188100 KB Output is correct
10 Correct 231 ms 188128 KB Output is correct
11 Correct 232 ms 188132 KB Output is correct
12 Correct 177 ms 188052 KB Output is correct
13 Correct 346 ms 188228 KB Output is correct
14 Correct 376 ms 188328 KB Output is correct
15 Correct 195 ms 188100 KB Output is correct
16 Correct 190 ms 188060 KB Output is correct
17 Correct 181 ms 188356 KB Output is correct
18 Correct 157 ms 188160 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 188240 KB Output is correct
2 Correct 200 ms 189080 KB Output is correct
3 Correct 409 ms 188608 KB Output is correct
4 Correct 196 ms 188088 KB Output is correct
5 Correct 312 ms 188484 KB Output is correct
6 Correct 184 ms 188236 KB Output is correct
7 Correct 176 ms 188236 KB Output is correct
8 Correct 194 ms 188164 KB Output is correct
9 Correct 334 ms 188584 KB Output is correct
10 Correct 410 ms 188596 KB Output is correct
11 Correct 414 ms 188420 KB Output is correct
12 Correct 240 ms 188096 KB Output is correct
13 Correct 164 ms 188160 KB Output is correct
14 Correct 220 ms 188168 KB Output is correct
15 Correct 361 ms 188336 KB Output is correct
16 Correct 206 ms 188872 KB Output is correct
17 Correct 358 ms 188080 KB Output is correct
18 Correct 336 ms 188876 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 188816 KB Output is correct
2 Correct 415 ms 188684 KB Output is correct
3 Correct 450 ms 189048 KB Output is correct
4 Correct 289 ms 189220 KB Output is correct
5 Correct 273 ms 189868 KB Output is correct
6 Correct 365 ms 189128 KB Output is correct
7 Correct 302 ms 189492 KB Output is correct
8 Correct 407 ms 188848 KB Output is correct
9 Correct 359 ms 188820 KB Output is correct
10 Correct 278 ms 188196 KB Output is correct
11 Correct 250 ms 188364 KB Output is correct
12 Correct 344 ms 188364 KB Output is correct
13 Correct 380 ms 189280 KB Output is correct
14 Correct 263 ms 189436 KB Output is correct
15 Correct 349 ms 188576 KB Output is correct
16 Correct 364 ms 188560 KB Output is correct
17 Correct 330 ms 188672 KB Output is correct
18 Correct 409 ms 188732 KB Output is correct
19 Correct 174 ms 188364 KB Output is correct
20 Correct 413 ms 189048 KB Output is correct
21 Correct 304 ms 189476 KB Output is correct
22 Correct 440 ms 189844 KB Output is correct
23 Correct 246 ms 189376 KB Output is correct
24 Correct 195 ms 189100 KB Output is correct
25 Correct 307 ms 189276 KB Output is correct
26 Correct 283 ms 189028 KB Output is correct
27 Correct 477 ms 189504 KB Output is correct
28 Correct 193 ms 189136 KB Output is correct
29 Correct 390 ms 189940 KB Output is correct
30 Correct 372 ms 189708 KB Output is correct
31 Correct 218 ms 189000 KB Output is correct
32 Correct 248 ms 189076 KB Output is correct
33 Correct 210 ms 189048 KB Output is correct
34 Correct 304 ms 189388 KB Output is correct
35 Correct 202 ms 189260 KB Output is correct
36 Correct 456 ms 189732 KB Output is correct
37 Correct 228 ms 189868 KB Output is correct
38 Correct 351 ms 189132 KB Output is correct
39 Correct 218 ms 189308 KB Output is correct
40 Correct 319 ms 189128 KB Output is correct
41 Correct 278 ms 189508 KB Output is correct
42 Correct 368 ms 189388 KB Output is correct