oj.uz

Submission #310131

# Submission time Handle Problem Language Result Execution time Memory
310131 2020-10-05T22:22:09 Z caoash Brunhilda’s Birthday (BOI13_brunhilda) C++14
45.7143 / 100
 1000 ms 11492 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 = 200005;
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

gp_hash_table<ll, ll> dp;
int n, m; 
vector<ll> prim;

ll solve(ll x) {
    if (dp.find(x) != dp.end()) {
        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 < 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 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 7 ms 1664 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 584 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 7 ms 512 KB Output is correct
14 Correct 53 ms 1712 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 7 ms 1660 KB Output is correct
18 Correct 8 ms 1664 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 12 ms 1500 KB Output is correct
3 Correct 9 ms 1532 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 9 ms 1532 KB Output is correct
10 Correct 9 ms 1532 KB Output is correct
11 Correct 9 ms 1024 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 6 ms 1024 KB Output is correct
16 Correct 12 ms 1532 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 13 ms 1532 KB Output is correct

Subtask #3
5.71428571429 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 1140 KB Time limit exceeded
2 Execution timed out 1090 ms 1136 KB Time limit exceeded
3 Execution timed out 1086 ms 1396 KB Time limit exceeded
4 Execution timed out 1090 ms 5376 KB Time limit exceeded
5 Execution timed out 1094 ms 1532 KB Time limit exceeded
6 Execution timed out 1086 ms 3104 KB Time limit exceeded
7 Execution timed out 1091 ms 1532 KB Time limit exceeded
8 Execution timed out 1082 ms 1272 KB Time limit exceeded
9 Execution timed out 1089 ms 1140 KB Time limit exceeded
10 Execution timed out 1084 ms 3100 KB Time limit exceeded
11 Execution timed out 1061 ms 5532 KB Time limit exceeded
12 Execution timed out 1087 ms 3104 KB Time limit exceeded
13 Execution timed out 1091 ms 1464 KB Time limit exceeded
14 Execution timed out 1095 ms 11492 KB Time limit exceeded
15 Execution timed out 1091 ms 3228 KB Time limit exceeded
16 Execution timed out 1084 ms 3100 KB Time limit exceeded
17 Execution timed out 1083 ms 1516 KB Time limit exceeded
18 Execution timed out 1089 ms 1268 KB Time limit exceeded
19 Correct 944 ms 3104 KB Output is correct
20 Execution timed out 1091 ms 1300 KB Time limit exceeded
21 Execution timed out 1090 ms 5616 KB Time limit exceeded
22 Execution timed out 1092 ms 1532 KB Time limit exceeded
23 Execution timed out 1071 ms 1592 KB Time limit exceeded
24 Correct 768 ms 10092 KB Output is correct
25 Execution timed out 1091 ms 5248 KB Time limit exceeded
26 Execution timed out 1061 ms 5248 KB Time limit exceeded
27 Execution timed out 1087 ms 1532 KB Time limit exceeded
28 Correct 721 ms 9960 KB Output is correct
29 Execution timed out 1093 ms 1532 KB Time limit exceeded
30 Execution timed out 1082 ms 1532 KB Time limit exceeded
31 Execution timed out 1097 ms 5272 KB Time limit exceeded
32 Execution timed out 1096 ms 5324 KB Time limit exceeded
33 Correct 759 ms 9964 KB Output is correct
34 Execution timed out 1091 ms 1532 KB Time limit exceeded
35 Execution timed out 1085 ms 10224 KB Time limit exceeded
36 Execution timed out 1096 ms 1532 KB Time limit exceeded
37 Execution timed out 1092 ms 1532 KB Time limit exceeded
38 Execution timed out 1095 ms 2956 KB Time limit exceeded
39 Execution timed out 1093 ms 9996 KB Time limit exceeded
40 Execution timed out 1093 ms 3016 KB Time limit exceeded
41 Execution timed out 1047 ms 1660 KB Time limit exceeded
42 Execution timed out 1093 ms 5344 KB Time limit exceeded