oj.uz

Submission #310130

# Submission time Handle Problem Language Result Execution time Memory
310130 2020-10-05T22:18:45 Z caoash Brunhilda’s Birthday (BOI13_brunhilda) C++14
43.4921 / 100
 1000 ms 12000 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);
            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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 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 Incorrect 1 ms 512 KB Output isn't correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 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 6 ms 512 KB Output is correct
14 Correct 52 ms 1656 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 6 ms 1660 KB Output is correct
18 Correct 7 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 11 ms 1532 KB Output is correct
3 Correct 9 ms 1532 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 6 ms 1024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 9 ms 1452 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 11 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 1097 ms 1140 KB Time limit exceeded
2 Execution timed out 1090 ms 1268 KB Time limit exceeded
3 Execution timed out 1034 ms 1176 KB Time limit exceeded
4 Execution timed out 1067 ms 5852 KB Time limit exceeded
5 Execution timed out 1081 ms 1532 KB Time limit exceeded
6 Execution timed out 1071 ms 2992 KB Time limit exceeded
7 Execution timed out 1083 ms 1532 KB Time limit exceeded
8 Execution timed out 1096 ms 1140 KB Time limit exceeded
9 Execution timed out 1097 ms 1140 KB Time limit exceeded
10 Execution timed out 1067 ms 3112 KB Time limit exceeded
11 Execution timed out 1066 ms 5400 KB Time limit exceeded
12 Execution timed out 1094 ms 3104 KB Time limit exceeded
13 Execution timed out 1093 ms 1464 KB Time limit exceeded
14 Execution timed out 1091 ms 12000 KB Time limit exceeded
15 Execution timed out 1093 ms 3232 KB Time limit exceeded
16 Execution timed out 1032 ms 2976 KB Time limit exceeded
17 Execution timed out 1088 ms 1652 KB Time limit exceeded
18 Execution timed out 1081 ms 1132 KB Time limit exceeded
19 Correct 939 ms 3104 KB Output is correct
20 Execution timed out 1053 ms 1140 KB Time limit exceeded
21 Execution timed out 1088 ms 6064 KB Time limit exceeded
22 Execution timed out 1093 ms 1532 KB Time limit exceeded
23 Execution timed out 1099 ms 1340 KB Time limit exceeded
24 Correct 768 ms 10760 KB Output is correct
25 Execution timed out 1094 ms 5600 KB Time limit exceeded
26 Execution timed out 1090 ms 5796 KB Time limit exceeded
27 Execution timed out 1080 ms 1532 KB Time limit exceeded
28 Correct 719 ms 10716 KB Output is correct
29 Execution timed out 1051 ms 1532 KB Time limit exceeded
30 Execution timed out 1090 ms 1532 KB Time limit exceeded
31 Execution timed out 1092 ms 5788 KB Time limit exceeded
32 Execution timed out 1090 ms 5636 KB Time limit exceeded
33 Correct 760 ms 10608 KB Output is correct
34 Execution timed out 1051 ms 1532 KB Time limit exceeded
35 Execution timed out 1094 ms 10732 KB Time limit exceeded
36 Execution timed out 1092 ms 1532 KB Time limit exceeded
37 Execution timed out 1089 ms 1532 KB Time limit exceeded
38 Execution timed out 1091 ms 3228 KB Time limit exceeded
39 Execution timed out 1091 ms 10748 KB Time limit exceeded
40 Execution timed out 1094 ms 3100 KB Time limit exceeded
41 Execution timed out 1095 ms 1532 KB Time limit exceeded
42 Execution timed out 1092 ms 6032 KB Time limit exceeded