oj.uz

Submission #310466

# Submission time Handle Problem Language Result Execution time Memory
310466 2020-10-07T04:28:20 Z caoash Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 988 ms 178292 KB 
#include <bits/stdc++.h> 
using namespace std;

using ll = long long;

using vi = vector<int>;
using vl = vector<ll>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

const ll MX = 20000005;
const int MOD = (int) (1e9 + 7);
const int INF = (int) 987654321;

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

namespace output {
  void pr(int x) {
    cout << x;
  }
  void pr(long x) {
    cout << x;
  }
  void pr(ll x) {
    cout << x;
  }
  void pr(unsigned x) {
    cout << x;
  }
  void pr(unsigned long x) {
    cout << x;
  }
  void pr(unsigned long long x) {
    cout << x;
  }
  void pr(float x) {
    cout << x;
  }
  void pr(double x) {
    cout << x;
  }
  void pr(long double x) {
    cout << x;
  }
  void pr(char x) {
    cout << x;
  }
  void pr(const char * x) {
    cout << x;
  }
  void pr(const string & x) {
    cout << x;
  }
  void pr(bool x) {
    pr(x ? "true" : "false");
  }

  template < class T1, class T2 > void pr(const pair < T1, T2 > & x);
  template < class T > void pr(const T & x);

  template < class T, class...Ts > void pr(const T & t,
    const Ts & ...ts) {
    pr(t);
    pr(ts...);
  }
  template < class T1, class T2 > void pr(const pair < T1, T2 > & x) {
    pr("{", x.f, ", ", x.s, "}");
  }
  template < class T > void pr(const T & x) {
    pr("{"); // const iterator needed for vector<bool>
    bool fst = 1;
    for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0;
    pr("}");
  }

  void ps() {
    pr("\n");
  } // print w/ spaces
  template < class T, class...Ts > void ps(const T & t,
    const Ts & ...ts) {
    pr(t);
    if (sizeof...(ts)) pr(" ");
    ps(ts...);
  }

  void pc() {
    cout << "]" << endl;
  } // debug w/ commas
  template < class T, class...Ts > void pc(const T & t,
    const Ts & ...ts) {
    pr(t);
    if (sizeof...(ts)) pr(", ");
    pc(ts...);
  }
  #define dbg(x...) pr("[", #x, "] = ["), pc(x);
}

#ifdef LOCAL
using namespace output;
#endif

int dp[MX];
int trans[MX];
bool has[MX];
int n, m; 
vector<int> prim;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        prim.pb(x);
    }
    for (int i = 0; i < n; i++) {
        for (int j = prim[i] - 1; j <= MX; j += prim[i]) {
            if (prim[i] - 1 > trans[j]) has[j] = true;
            trans[j] = max(trans[j], prim[i] - 1);
        }
    }
    for (int i = 1; i < MX; i++) {
        if (has[i - 1]) {
            trans[i] = max(trans[i], 0);
        } else {
            trans[i] = max(trans[i], trans[i - 1]);
        }
    }
    for (int i = 0; i < MX; i++) dp[i] = INF;
    dp[0] = 0;
    for (int i = 1; i < MX; i++) {
        int best = i - trans[i];
        if (best == INF) {
            dp[i] = INF;
        } else {
            dp[i] = min(INF, dp[best] + 1);
        }
    }
    for (int i = 0; i < m; i++) {
        int v; cin >> v;
        int ans = dp[v];
        if (ans == INF) cout << "oo" << '\n';
        else cout << ans << '\n';
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 210 ms 176504 KB Output isn't correct
2 Incorrect 320 ms 176504 KB Output isn't correct
3 Incorrect 253 ms 176504 KB Output isn't correct
4 Incorrect 237 ms 176632 KB Output isn't correct
5 Incorrect 276 ms 176504 KB Output isn't correct
6 Incorrect 214 ms 176504 KB Output isn't correct
7 Incorrect 247 ms 176424 KB Output isn't correct
8 Incorrect 290 ms 176488 KB Output isn't correct
9 Incorrect 323 ms 176440 KB Output isn't correct
10 Incorrect 387 ms 176504 KB Output isn't correct
11 Incorrect 381 ms 176504 KB Output isn't correct
12 Incorrect 225 ms 176504 KB Output isn't correct
13 Incorrect 678 ms 176504 KB Output isn't correct
14 Incorrect 684 ms 176504 KB Output isn't correct
15 Incorrect 332 ms 176632 KB Output isn't correct
16 Incorrect 315 ms 176504 KB Output isn't correct
17 Incorrect 325 ms 176504 KB Output isn't correct
18 Incorrect 234 ms 176632 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 296 ms 176504 KB Output isn't correct
2 Incorrect 359 ms 177140 KB Output isn't correct
3 Incorrect 882 ms 177012 KB Output isn't correct
4 Incorrect 396 ms 176504 KB Output isn't correct
5 Incorrect 644 ms 176760 KB Output isn't correct
6 Incorrect 308 ms 176564 KB Output isn't correct
7 Incorrect 301 ms 176504 KB Output isn't correct
8 Incorrect 393 ms 176632 KB Output isn't correct
9 Incorrect 752 ms 176884 KB Output isn't correct
10 Incorrect 903 ms 176872 KB Output isn't correct
11 Incorrect 881 ms 176744 KB Output isn't correct
12 Incorrect 500 ms 176632 KB Output isn't correct
13 Incorrect 245 ms 176636 KB Output isn't correct
14 Incorrect 402 ms 176480 KB Output isn't correct
15 Incorrect 718 ms 176760 KB Output isn't correct
16 Incorrect 357 ms 176884 KB Output isn't correct
17 Incorrect 719 ms 176608 KB Output isn't correct
18 Incorrect 738 ms 176912 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 726 ms 177036 KB Output isn't correct
2 Incorrect 896 ms 176920 KB Output isn't correct
3 Incorrect 893 ms 177272 KB Output isn't correct
4 Incorrect 512 ms 177436 KB Output isn't correct
5 Incorrect 440 ms 178036 KB Output isn't correct
6 Incorrect 708 ms 177400 KB Output isn't correct
7 Incorrect 716 ms 177524 KB Output isn't correct
8 Incorrect 708 ms 177144 KB Output isn't correct
9 Incorrect 715 ms 177144 KB Output isn't correct
10 Incorrect 598 ms 176528 KB Output isn't correct
11 Incorrect 523 ms 176632 KB Output isn't correct
12 Incorrect 653 ms 176760 KB Output isn't correct
13 Incorrect 845 ms 177584 KB Output isn't correct
14 Incorrect 448 ms 177528 KB Output isn't correct
15 Incorrect 691 ms 176676 KB Output isn't correct
16 Incorrect 782 ms 176636 KB Output isn't correct
17 Incorrect 716 ms 176760 KB Output isn't correct
18 Incorrect 946 ms 176892 KB Output isn't correct
19 Incorrect 284 ms 176632 KB Output isn't correct
20 Incorrect 924 ms 177272 KB Output isn't correct
21 Incorrect 520 ms 177528 KB Output isn't correct
22 Incorrect 946 ms 178292 KB Output isn't correct
23 Incorrect 416 ms 177656 KB Output isn't correct
24 Incorrect 298 ms 177528 KB Output isn't correct
25 Incorrect 584 ms 177400 KB Output isn't correct
26 Incorrect 506 ms 177384 KB Output isn't correct
27 Incorrect 988 ms 177704 KB Output isn't correct
28 Incorrect 298 ms 177656 KB Output isn't correct
29 Incorrect 869 ms 178164 KB Output isn't correct
30 Incorrect 802 ms 177888 KB Output isn't correct
31 Incorrect 384 ms 177400 KB Output isn't correct
32 Incorrect 441 ms 177528 KB Output isn't correct
33 Incorrect 251 ms 177400 KB Output isn't correct
34 Incorrect 721 ms 177524 KB Output isn't correct
35 Incorrect 343 ms 177528 KB Output isn't correct
36 Incorrect 930 ms 178164 KB Output isn't correct
37 Incorrect 430 ms 178036 KB Output isn't correct
38 Incorrect 707 ms 177400 KB Output isn't correct
39 Incorrect 347 ms 177528 KB Output isn't correct
40 Incorrect 618 ms 177400 KB Output isn't correct
41 Incorrect 618 ms 177536 KB Output isn't correct
42 Incorrect 772 ms 177528 KB Output isn't correct