oj.uz

Submission #305845

# Submission time Handle Problem Language Result Execution time Memory
305845 2020-09-24T02:35:30 Z HynDuf Brunhilda’s Birthday (BOI13_brunhilda) C++11
77.4603 / 100
 314 ms 40056 KB 
#include <bits/stdc++.h>

#define task "B"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 1e5 + 2, NN = 1e7 + 2;
int n, q, dp[NN + 2];
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> q;
    ll lcm = 1;
    rep(i, 1, n)
    {
        int p;
        cin >> p;
        for (int j = p - 1; j <= NN; j += p) dp[j] = p - 1;
        lcm = min(N * 100LL, lcm * p);
    }
    Rep(i, NN - 1, 1) dp[i] = max(dp[i], dp[i + 1] - 1);
    rep(i, 1, NN) dp[i] = dp[i - dp[i]] + 1;
    while (q--)
    {
        int x;
        cin >> x;
        if (x >= lcm) cout << "oo\n";
        else cout << dp[x] << '\n';
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 39424 KB Output is correct
2 Correct 103 ms 39424 KB Output is correct
3 Correct 93 ms 39424 KB Output is correct
4 Correct 85 ms 39544 KB Output is correct
5 Correct 102 ms 39544 KB Output is correct
6 Correct 83 ms 39456 KB Output is correct
7 Correct 93 ms 39424 KB Output is correct
8 Correct 102 ms 39516 KB Output is correct
9 Correct 111 ms 39424 KB Output is correct
10 Correct 134 ms 39516 KB Output is correct
11 Correct 127 ms 39424 KB Output is correct
12 Correct 86 ms 39512 KB Output is correct
13 Correct 219 ms 39672 KB Output is correct
14 Correct 226 ms 39520 KB Output is correct
15 Correct 112 ms 39512 KB Output is correct
16 Correct 101 ms 39452 KB Output is correct
17 Correct 106 ms 39544 KB Output is correct
18 Correct 82 ms 39424 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 39424 KB Output is correct
2 Correct 129 ms 39424 KB Output is correct
3 Correct 281 ms 39424 KB Output is correct
4 Correct 118 ms 39424 KB Output is correct
5 Correct 197 ms 39424 KB Output is correct
6 Correct 102 ms 39456 KB Output is correct
7 Correct 101 ms 39424 KB Output is correct
8 Correct 119 ms 39520 KB Output is correct
9 Correct 235 ms 39752 KB Output is correct
10 Correct 288 ms 39544 KB Output is correct
11 Incorrect 273 ms 39544 KB Output isn't correct
12 Correct 155 ms 39544 KB Output is correct
13 Correct 88 ms 39424 KB Output is correct
14 Correct 120 ms 39544 KB Output is correct
15 Correct 233 ms 39416 KB Output is correct
16 Correct 120 ms 39424 KB Output is correct
17 Correct 230 ms 39544 KB Output is correct
18 Correct 239 ms 39424 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 39520 KB Output is correct
2 Correct 295 ms 39520 KB Output is correct
3 Correct 302 ms 39644 KB Output is correct
4 Incorrect 189 ms 39776 KB Output isn't correct
5 Incorrect 150 ms 39608 KB Output isn't correct
6 Correct 256 ms 39800 KB Output is correct
7 Correct 215 ms 39544 KB Output is correct
8 Correct 236 ms 39544 KB Output is correct
9 Correct 237 ms 39544 KB Output is correct
10 Correct 184 ms 39520 KB Output is correct
11 Incorrect 161 ms 39548 KB Output isn't correct
12 Correct 215 ms 39544 KB Output is correct
13 Correct 278 ms 39800 KB Output is correct
14 Correct 166 ms 40056 KB Output is correct
15 Incorrect 228 ms 39544 KB Output isn't correct
16 Correct 250 ms 39544 KB Output is correct
17 Correct 224 ms 39544 KB Output is correct
18 Correct 289 ms 39544 KB Output is correct
19 Incorrect 101 ms 39520 KB Output isn't correct
20 Correct 294 ms 39672 KB Output is correct
21 Incorrect 186 ms 40056 KB Output isn't correct
22 Correct 294 ms 39672 KB Output is correct
23 Correct 144 ms 39800 KB Output is correct
24 Correct 121 ms 39780 KB Output is correct
25 Incorrect 204 ms 39928 KB Output isn't correct
26 Incorrect 187 ms 39672 KB Output isn't correct
27 Correct 314 ms 39520 KB Output is correct
28 Incorrect 121 ms 39800 KB Output isn't correct
29 Correct 301 ms 39644 KB Output is correct
30 Correct 263 ms 39648 KB Output is correct
31 Correct 142 ms 39672 KB Output is correct
32 Incorrect 152 ms 39780 KB Output isn't correct
33 Incorrect 107 ms 39672 KB Output isn't correct
34 Correct 218 ms 39544 KB Output is correct
35 Incorrect 133 ms 39800 KB Output isn't correct
36 Correct 294 ms 39672 KB Output is correct
37 Incorrect 149 ms 39672 KB Output isn't correct
38 Correct 248 ms 39800 KB Output is correct
39 Incorrect 135 ms 39800 KB Output isn't correct
40 Correct 211 ms 39672 KB Output is correct
41 Correct 194 ms 39520 KB Output is correct
42 Incorrect 266 ms 39928 KB Output isn't correct