oj.uz

Submission #310457

# Submission time Handle Problem Language Result Execution time Memory
310457 2020-10-07T04:02:13 Z caoash Brunhilda’s Birthday (BOI13_brunhilda) C++14
2.22222 / 100
 1000 ms 158448 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 int MX = 20000005;
const int MOD = (int) (1e9 + 7);
const ll INF = (ll) 1e18;

#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

ll dp[MX];
int n, m; 
vector<ll> prim;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        prim.pb(x);
    }
    for (int i = 0; i < MX; i++) dp[i] = INT_MAX;
    dp[0] = 0;
    for (ll i = 1; i < MX; i++) {
        ll best = INF;
        for (auto p : prim) {
            ll to = i - (i % p);
            if (to != i) best = min(best, to);
        }
        if (best == INF) {
            dp[i] = INF;
        } else {
            dp[i] = min(INF, dp[best] + 1);
        }
    }
    for (int i = 0; i < m; i++) {
        ll v; cin >> v;
        ll ans = dp[v];
        if (ans == INF) cout << "oo" << '\n';
        else cout << ans << '\n';
    }
}

Subtask #1
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 656 ms 156920 KB Output is correct
2 Execution timed out 1053 ms 156924 KB Time limit exceeded
3 Execution timed out 1006 ms 156920 KB Time limit exceeded
4 Execution timed out 1066 ms 156840 KB Time limit exceeded
5 Execution timed out 1110 ms 156920 KB Time limit exceeded
6 Correct 644 ms 157048 KB Output is correct
7 Execution timed out 1004 ms 156936 KB Time limit exceeded
8 Execution timed out 1096 ms 156920 KB Time limit exceeded
9 Execution timed out 1053 ms 157104 KB Time limit exceeded
10 Execution timed out 1063 ms 156920 KB Time limit exceeded
11 Execution timed out 1060 ms 156920 KB Time limit exceeded
12 Execution timed out 1064 ms 156920 KB Time limit exceeded
13 Execution timed out 1104 ms 156920 KB Time limit exceeded
14 Execution timed out 1109 ms 156920 KB Time limit exceeded
15 Execution timed out 1063 ms 156920 KB Time limit exceeded
16 Execution timed out 1085 ms 156920 KB Time limit exceeded
17 Execution timed out 1101 ms 156920 KB Time limit exceeded
18 Execution timed out 1098 ms 156920 KB Time limit exceeded

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 157176 KB Time limit exceeded
2 Execution timed out 1105 ms 158316 KB Time limit exceeded
3 Execution timed out 1103 ms 158064 KB Time limit exceeded
4 Execution timed out 1110 ms 156920 KB Time limit exceeded
5 Execution timed out 1109 ms 157808 KB Time limit exceeded
6 Execution timed out 1108 ms 156920 KB Time limit exceeded
7 Execution timed out 1098 ms 157176 KB Time limit exceeded
8 Execution timed out 1107 ms 156920 KB Time limit exceeded
9 Execution timed out 1108 ms 158064 KB Time limit exceeded
10 Execution timed out 1111 ms 158060 KB Time limit exceeded
11 Execution timed out 1105 ms 157556 KB Time limit exceeded
12 Execution timed out 1096 ms 156920 KB Time limit exceeded
13 Execution timed out 1096 ms 156920 KB Time limit exceeded
14 Execution timed out 1100 ms 156920 KB Time limit exceeded
15 Execution timed out 1105 ms 157684 KB Time limit exceeded
16 Execution timed out 1104 ms 158320 KB Time limit exceeded
17 Execution timed out 1103 ms 156920 KB Time limit exceeded
18 Execution timed out 1107 ms 158448 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1107 ms 157940 KB Time limit exceeded
2 Execution timed out 1105 ms 157940 KB Time limit exceeded
3 Execution timed out 1108 ms 157940 KB Time limit exceeded
4 Execution timed out 1098 ms 157048 KB Time limit exceeded
5 Execution timed out 1108 ms 158320 KB Time limit exceeded
6 Execution timed out 1109 ms 157304 KB Time limit exceeded
7 Execution timed out 1107 ms 158320 KB Time limit exceeded
8 Execution timed out 1105 ms 157940 KB Time limit exceeded
9 Execution timed out 1104 ms 157936 KB Time limit exceeded
10 Execution timed out 1105 ms 157048 KB Time limit exceeded
11 Execution timed out 1100 ms 157176 KB Time limit exceeded
12 Execution timed out 1105 ms 157048 KB Time limit exceeded
13 Execution timed out 1100 ms 157560 KB Time limit exceeded
14 Execution timed out 1104 ms 156920 KB Time limit exceeded
15 Execution timed out 1107 ms 157048 KB Time limit exceeded
16 Execution timed out 1099 ms 157052 KB Time limit exceeded
17 Execution timed out 1102 ms 157812 KB Time limit exceeded
18 Execution timed out 1078 ms 157944 KB Time limit exceeded
19 Execution timed out 1101 ms 157048 KB Time limit exceeded
20 Execution timed out 1102 ms 158068 KB Time limit exceeded
21 Execution timed out 1099 ms 156920 KB Time limit exceeded
22 Execution timed out 1101 ms 158448 KB Time limit exceeded
23 Execution timed out 1097 ms 157560 KB Time limit exceeded
24 Execution timed out 1103 ms 156920 KB Time limit exceeded
25 Execution timed out 1099 ms 157048 KB Time limit exceeded
26 Execution timed out 1107 ms 157048 KB Time limit exceeded
27 Execution timed out 1098 ms 158320 KB Time limit exceeded
28 Execution timed out 1103 ms 156920 KB Time limit exceeded
29 Execution timed out 1046 ms 158316 KB Time limit exceeded
30 Execution timed out 1097 ms 158188 KB Time limit exceeded
31 Execution timed out 1110 ms 157048 KB Time limit exceeded
32 Execution timed out 1047 ms 157048 KB Time limit exceeded
33 Execution timed out 1107 ms 156920 KB Time limit exceeded
34 Execution timed out 1100 ms 158320 KB Time limit exceeded
35 Execution timed out 1108 ms 156920 KB Time limit exceeded
36 Execution timed out 1096 ms 158192 KB Time limit exceeded
37 Execution timed out 1089 ms 158320 KB Time limit exceeded
38 Execution timed out 1104 ms 157304 KB Time limit exceeded
39 Execution timed out 1102 ms 156920 KB Time limit exceeded
40 Execution timed out 1108 ms 157304 KB Time limit exceeded
41 Execution timed out 1107 ms 158316 KB Time limit exceeded
42 Execution timed out 1105 ms 157048 KB Time limit exceeded