oj.uz

Submission #310133

# Submission time Handle Problem Language Result Execution time Memory
310133 2020-10-05T22:30:31 Z caoash Brunhilda’s Birthday (BOI13_brunhilda) C++14
47.1429 / 100
 1000 ms 158456 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;

ll solve(ll x) {
    if (dp[x] != -1) {
        return dp[x];
    } else if (x == 0) {
        return dp[x] = 0;
    } else {
        ll curr = INT_MAX;
        for (auto p : prim) {
            ll to = x - (x % p);
            if (to != x) curr = min(curr, to);
        }
        if (curr == INT_MAX) {
            return dp[x] = curr;
        } else {
            ll go = solve(curr);
            if (go == INT_MAX) return dp[x] = INT_MAX;
            else return dp[x] = go + 1;
        }
    }
}

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] = -1;
    for (int i = 0; i < m; i++) {
        ll v; cin >> v;
        ll ans = solve(v);
        if (ans == INT_MAX) cout << "oo" << '\n';
        else cout << ans << '\n';
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 156920 KB Output is correct
2 Correct 82 ms 156920 KB Output is correct
3 Correct 82 ms 156920 KB Output is correct
4 Correct 85 ms 157048 KB Output is correct
5 Correct 83 ms 156920 KB Output is correct
6 Correct 81 ms 156920 KB Output is correct
7 Correct 82 ms 156920 KB Output is correct
8 Correct 84 ms 156992 KB Output is correct
9 Correct 85 ms 156860 KB Output is correct
10 Correct 82 ms 156880 KB Output is correct
11 Correct 91 ms 156920 KB Output is correct
12 Correct 97 ms 156920 KB Output is correct
13 Correct 88 ms 156924 KB Output is correct
14 Correct 136 ms 156924 KB Output is correct
15 Correct 80 ms 156924 KB Output is correct
16 Correct 81 ms 156920 KB Output is correct
17 Correct 87 ms 156924 KB Output is correct
18 Correct 89 ms 156920 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 157048 KB Output is correct
2 Correct 92 ms 157736 KB Output is correct
3 Correct 89 ms 157424 KB Output is correct
4 Correct 84 ms 156920 KB Output is correct
5 Correct 91 ms 157424 KB Output is correct
6 Correct 82 ms 156920 KB Output is correct
7 Correct 83 ms 157120 KB Output is correct
8 Correct 85 ms 156920 KB Output is correct
9 Correct 89 ms 157548 KB Output is correct
10 Correct 90 ms 157536 KB Output is correct
11 Correct 90 ms 157300 KB Output is correct
12 Correct 90 ms 156920 KB Output is correct
13 Correct 85 ms 156920 KB Output is correct
14 Correct 83 ms 156920 KB Output is correct
15 Correct 86 ms 157428 KB Output is correct
16 Correct 91 ms 157680 KB Output is correct
17 Correct 89 ms 157048 KB Output is correct
18 Correct 94 ms 157812 KB Output is correct

Subtask #3
7.14285714286 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1101 ms 157428 KB Time limit exceeded
2 Execution timed out 1108 ms 157420 KB Time limit exceeded
3 Execution timed out 1105 ms 157476 KB Time limit exceeded
4 Execution timed out 1101 ms 157304 KB Time limit exceeded
5 Execution timed out 1095 ms 157804 KB Time limit exceeded
6 Execution timed out 1104 ms 157072 KB Time limit exceeded
7 Execution timed out 1097 ms 157936 KB Time limit exceeded
8 Execution timed out 1102 ms 157556 KB Time limit exceeded
9 Execution timed out 1094 ms 157428 KB Time limit exceeded
10 Execution timed out 1097 ms 157304 KB Time limit exceeded
11 Execution timed out 1107 ms 157176 KB Time limit exceeded
12 Execution timed out 1106 ms 157180 KB Time limit exceeded
13 Execution timed out 1098 ms 157328 KB Time limit exceeded
14 Correct 141 ms 158456 KB Output is correct
15 Execution timed out 1107 ms 157176 KB Time limit exceeded
16 Execution timed out 1109 ms 157052 KB Time limit exceeded
17 Execution timed out 1110 ms 157424 KB Time limit exceeded
18 Execution timed out 1110 ms 157428 KB Time limit exceeded
19 Execution timed out 1066 ms 157048 KB Time limit exceeded
20 Execution timed out 1110 ms 157428 KB Time limit exceeded
21 Correct 197 ms 157816 KB Output is correct
22 Execution timed out 1110 ms 157808 KB Time limit exceeded
23 Execution timed out 1107 ms 157304 KB Time limit exceeded
24 Correct 843 ms 157304 KB Output is correct
25 Execution timed out 1068 ms 157048 KB Time limit exceeded
26 Execution timed out 1108 ms 157048 KB Time limit exceeded
27 Execution timed out 1106 ms 157936 KB Time limit exceeded
28 Correct 780 ms 157304 KB Output is correct
29 Execution timed out 1099 ms 157812 KB Time limit exceeded
30 Execution timed out 1061 ms 157548 KB Time limit exceeded
31 Execution timed out 1109 ms 157112 KB Time limit exceeded
32 Execution timed out 1089 ms 157288 KB Time limit exceeded
33 Correct 834 ms 157176 KB Output is correct
34 Execution timed out 1109 ms 157808 KB Time limit exceeded
35 Execution timed out 1109 ms 157176 KB Time limit exceeded
36 Execution timed out 1109 ms 157680 KB Time limit exceeded
37 Execution timed out 1109 ms 157804 KB Time limit exceeded
38 Execution timed out 1098 ms 157304 KB Time limit exceeded
39 Execution timed out 1093 ms 157460 KB Time limit exceeded
40 Execution timed out 1107 ms 157176 KB Time limit exceeded
41 Execution timed out 1100 ms 157932 KB Time limit exceeded
42 Execution timed out 1110 ms 157176 KB Time limit exceeded