oj.uz

Submission #727459

# Submission time Handle Problem Language Result Execution time Memory
727459 2023-04-20T19:00:31 Z TB_ Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 265 ms 41648 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<(int)n;i++)
#define Fo(i, k, n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define sp(x, y) fixed<<setprecision(y)<<x
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define trr(it, x) for(auto it = x.rbegin(); it != x.rend(); it+)
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;


int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit); // remove if to endof file

    int n, q, val;
    cin >> n >> q;
    vi v;
    fo(i, n){
        cin >> val;
        v.pb(val);
    }
    int siz = 10000000;
    vi biggest(siz+1, -1);
    fo(i, v.size()){
        for(int j = 0; j<=siz; j+=v[i]) biggest[j] = max(biggest[j], v[i]);
    }

    int last = biggest[0];
    int next = 0;
    int c = 1;
    for(int i = 1; i<=siz;i++){
        last--;
        next--;
        if(!last){
            swap(last, next);
            c++;
        }
        next = max(next, biggest[i]);
        biggest[i] = (last<=0?-1:c);
    }
    
    while(q--){
        cin >> val;
        int ans = biggest[val];
        if(ans == -1) cout << "oo\n";
        else cout << ans << "\n";
    }

    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 39476 KB Output is correct
2 Correct 81 ms 39388 KB Output is correct
3 Correct 63 ms 39380 KB Output is correct
4 Correct 39 ms 39516 KB Output is correct
5 Correct 54 ms 39360 KB Output is correct
6 Correct 40 ms 39424 KB Output is correct
7 Correct 65 ms 39364 KB Output is correct
8 Correct 74 ms 39412 KB Output is correct
9 Correct 94 ms 39384 KB Output is correct
10 Correct 110 ms 39356 KB Output is correct
11 Correct 89 ms 39528 KB Output is correct
12 Correct 36 ms 39436 KB Output is correct
13 Correct 181 ms 39380 KB Output is correct
14 Correct 181 ms 39520 KB Output is correct
15 Correct 82 ms 39432 KB Output is correct
16 Correct 83 ms 39440 KB Output is correct
17 Correct 59 ms 39508 KB Output is correct
18 Correct 39 ms 39456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 39604 KB Output is correct
2 Correct 63 ms 40652 KB Output is correct
3 Correct 241 ms 40336 KB Output is correct
4 Correct 70 ms 39508 KB Output is correct
5 Correct 137 ms 40260 KB Output is correct
6 Correct 72 ms 39380 KB Output is correct
7 Correct 49 ms 39632 KB Output is correct
8 Correct 72 ms 39508 KB Output is correct
9 Correct 169 ms 40308 KB Output is correct
10 Correct 226 ms 40412 KB Output is correct
11 Correct 233 ms 39888 KB Output is correct
12 Correct 118 ms 39496 KB Output is correct
13 Correct 48 ms 39456 KB Output is correct
14 Correct 70 ms 39508 KB Output is correct
15 Correct 173 ms 40124 KB Output is correct
16 Correct 68 ms 40632 KB Output is correct
17 Correct 201 ms 39484 KB Output is correct
18 Correct 175 ms 40636 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 40404 KB Output is correct
2 Correct 265 ms 40300 KB Output is correct
3 Correct 241 ms 40684 KB Output is correct
4 Correct 138 ms 40396 KB Output is correct
5 Correct 83 ms 41628 KB Output is correct
6 Correct 199 ms 40532 KB Output is correct
7 Correct 141 ms 41160 KB Output is correct
8 Correct 185 ms 40408 KB Output is correct
9 Correct 206 ms 40404 KB Output is correct
10 Correct 132 ms 39632 KB Output is correct
11 Correct 109 ms 39744 KB Output is correct
12 Correct 175 ms 39656 KB Output is correct
13 Correct 220 ms 40912 KB Output is correct
14 Correct 130 ms 40652 KB Output is correct
15 Correct 180 ms 39748 KB Output is correct
16 Correct 204 ms 39724 KB Output is correct
17 Correct 159 ms 40156 KB Output is correct
18 Correct 228 ms 40288 KB Output is correct
19 Correct 61 ms 39752 KB Output is correct
20 Correct 249 ms 40656 KB Output is correct
21 Correct 152 ms 40784 KB Output is correct
22 Correct 243 ms 41648 KB Output is correct
23 Correct 88 ms 40908 KB Output is correct
24 Correct 73 ms 40408 KB Output is correct
25 Correct 154 ms 40448 KB Output is correct
26 Correct 133 ms 40396 KB Output is correct
27 Correct 259 ms 41112 KB Output is correct
28 Correct 77 ms 40528 KB Output is correct
29 Correct 204 ms 41628 KB Output is correct
30 Correct 194 ms 41424 KB Output is correct
31 Correct 84 ms 40384 KB Output is correct
32 Correct 116 ms 40492 KB Output is correct
33 Correct 62 ms 40380 KB Output is correct
34 Correct 147 ms 41240 KB Output is correct
35 Correct 76 ms 40452 KB Output is correct
36 Correct 238 ms 41424 KB Output is correct
37 Correct 81 ms 41604 KB Output is correct
38 Correct 192 ms 40492 KB Output is correct
39 Correct 80 ms 40488 KB Output is correct
40 Correct 160 ms 40476 KB Output is correct
41 Correct 136 ms 41244 KB Output is correct
42 Correct 207 ms 40616 KB Output is correct