oj.uz

Submission #369432

# Submission time Handle Problem Language Result Execution time Memory
369432 2021-02-21T16:37:15 Z ACmachine Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 671 ms 158060 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}

    
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
    const int mx = 2e7 + 120;
	int m, q;
    cin >> m >> q;
    vi p(m); cin >> p;
    vi n(q); cin >> n;
    vector<int> re(mx, 0);
    REP(i, m){
        for(int j = p[i] - 1; j < mx; j += p[i])
            re[j] = p[i] - 1;
    }
    REPD(i, mx - 5){
        if(re[i] < re[i + 1] - 1) 
            re[i] = re[i + 1] - 1;
    }
    vector<int> dp(mx, INF);
    dp[0] = 0;
    FOR(i, 1, mx, 1){
        if(re[i] == 0) continue;
        dp[i] = dp[i - re[i]] + 1;
    }
    REP(i, q){
        if(dp[n[i]] >= INF) cout << "oo" << "\n";
        else cout << dp[n[i]] << "\n";
    }
	
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 156908 KB Output is correct
2 Correct 283 ms 156908 KB Output is correct
3 Correct 250 ms 156908 KB Output is correct
4 Correct 203 ms 156908 KB Output is correct
5 Correct 241 ms 157036 KB Output is correct
6 Correct 214 ms 156884 KB Output is correct
7 Correct 240 ms 157036 KB Output is correct
8 Correct 282 ms 157056 KB Output is correct
9 Correct 322 ms 156876 KB Output is correct
10 Correct 344 ms 156908 KB Output is correct
11 Correct 311 ms 156908 KB Output is correct
12 Correct 196 ms 156908 KB Output is correct
13 Correct 518 ms 157036 KB Output is correct
14 Correct 513 ms 157036 KB Output is correct
15 Correct 294 ms 156908 KB Output is correct
16 Correct 284 ms 156908 KB Output is correct
17 Correct 255 ms 156908 KB Output is correct
18 Correct 201 ms 156908 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 156968 KB Output is correct
2 Correct 252 ms 157368 KB Output is correct
3 Correct 606 ms 157164 KB Output is correct
4 Correct 275 ms 156908 KB Output is correct
5 Correct 432 ms 157304 KB Output is correct
6 Correct 264 ms 156908 KB Output is correct
7 Correct 229 ms 156908 KB Output is correct
8 Correct 270 ms 156908 KB Output is correct
9 Correct 484 ms 157164 KB Output is correct
10 Correct 580 ms 157164 KB Output is correct
11 Correct 602 ms 157040 KB Output is correct
12 Correct 347 ms 156908 KB Output is correct
13 Correct 218 ms 156968 KB Output is correct
14 Correct 279 ms 156892 KB Output is correct
15 Correct 507 ms 157036 KB Output is correct
16 Correct 253 ms 157292 KB Output is correct
17 Correct 526 ms 156932 KB Output is correct
18 Correct 485 ms 157292 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 157420 KB Output is correct
2 Correct 596 ms 157188 KB Output is correct
3 Correct 622 ms 157420 KB Output is correct
4 Correct 399 ms 157548 KB Output is correct
5 Correct 285 ms 157932 KB Output is correct
6 Correct 524 ms 157548 KB Output is correct
7 Correct 431 ms 157636 KB Output is correct
8 Correct 516 ms 157420 KB Output is correct
9 Correct 522 ms 157364 KB Output is correct
10 Correct 400 ms 156940 KB Output is correct
11 Correct 345 ms 157036 KB Output is correct
12 Correct 469 ms 157036 KB Output is correct
13 Correct 592 ms 157616 KB Output is correct
14 Correct 368 ms 157804 KB Output is correct
15 Correct 480 ms 157088 KB Output is correct
16 Correct 553 ms 157124 KB Output is correct
17 Correct 470 ms 157164 KB Output is correct
18 Correct 620 ms 157292 KB Output is correct
19 Correct 244 ms 157036 KB Output is correct
20 Correct 624 ms 157420 KB Output is correct
21 Correct 425 ms 157932 KB Output is correct
22 Correct 646 ms 158060 KB Output is correct
23 Correct 301 ms 157676 KB Output is correct
24 Correct 286 ms 157548 KB Output is correct
25 Correct 417 ms 157548 KB Output is correct
26 Correct 394 ms 157548 KB Output is correct
27 Correct 671 ms 157548 KB Output is correct
28 Correct 260 ms 157548 KB Output is correct
29 Correct 562 ms 157932 KB Output is correct
30 Correct 537 ms 157932 KB Output is correct
31 Correct 291 ms 157420 KB Output is correct
32 Correct 318 ms 157596 KB Output is correct
33 Correct 233 ms 157548 KB Output is correct
34 Correct 428 ms 157804 KB Output is correct
35 Correct 272 ms 157676 KB Output is correct
36 Correct 615 ms 157932 KB Output is correct
37 Correct 284 ms 157932 KB Output is correct
38 Correct 513 ms 157548 KB Output is correct
39 Correct 267 ms 157548 KB Output is correct
40 Correct 438 ms 157548 KB Output is correct
41 Correct 400 ms 157548 KB Output is correct
42 Correct 566 ms 157676 KB Output is correct