oj.uz

Submission #305841

# Submission time Handle Problem Language Result Execution time Memory
305841 2020-09-24T02:32:54 Z HynDuf Brunhilda’s Birthday (BOI13_brunhilda) C++11
0 / 100
 1000 ms 79960 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 = 2e7 - 1;
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++) 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 78676 KB Output isn't correct
2 Incorrect 709 ms 78712 KB Output isn't correct
3 Incorrect 216 ms 78584 KB Output isn't correct
4 Execution timed out 1102 ms 78584 KB Time limit exceeded
5 Incorrect 284 ms 78660 KB Output isn't correct
6 Incorrect 187 ms 78584 KB Output isn't correct
7 Incorrect 215 ms 78668 KB Output isn't correct
8 Incorrect 229 ms 78716 KB Output isn't correct
9 Incorrect 299 ms 78584 KB Output isn't correct
10 Incorrect 428 ms 78668 KB Output isn't correct
11 Incorrect 430 ms 78584 KB Output isn't correct
12 Execution timed out 1093 ms 78584 KB Time limit exceeded
13 Execution timed out 1091 ms 78584 KB Time limit exceeded
14 Execution timed out 1090 ms 78584 KB Time limit exceeded
15 Incorrect 564 ms 78584 KB Output isn't correct
16 Incorrect 729 ms 78664 KB Output isn't correct
17 Incorrect 861 ms 78712 KB Output isn't correct
18 Execution timed out 1089 ms 78588 KB Time limit exceeded

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 78584 KB Time limit exceeded
2 Execution timed out 1096 ms 78584 KB Time limit exceeded
3 Execution timed out 1096 ms 78584 KB Time limit exceeded
4 Execution timed out 1099 ms 78584 KB Time limit exceeded
5 Execution timed out 1098 ms 78584 KB Time limit exceeded
6 Execution timed out 1098 ms 78584 KB Time limit exceeded
7 Execution timed out 1094 ms 78712 KB Time limit exceeded
8 Execution timed out 1095 ms 78584 KB Time limit exceeded
9 Execution timed out 1090 ms 78584 KB Time limit exceeded
10 Execution timed out 1078 ms 78712 KB Time limit exceeded
11 Execution timed out 1099 ms 78584 KB Time limit exceeded
12 Execution timed out 1101 ms 78584 KB Time limit exceeded
13 Execution timed out 1098 ms 78584 KB Time limit exceeded
14 Execution timed out 1065 ms 78584 KB Time limit exceeded
15 Execution timed out 1103 ms 78584 KB Time limit exceeded
16 Execution timed out 1047 ms 78616 KB Time limit exceeded
17 Execution timed out 1087 ms 78584 KB Time limit exceeded
18 Execution timed out 1099 ms 78604 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 78580 KB Time limit exceeded
2 Execution timed out 1094 ms 78584 KB Time limit exceeded
3 Execution timed out 1099 ms 78556 KB Time limit exceeded
4 Execution timed out 1057 ms 78584 KB Time limit exceeded
5 Execution timed out 1097 ms 78584 KB Time limit exceeded
6 Execution timed out 1097 ms 78584 KB Time limit exceeded
7 Execution timed out 1104 ms 78584 KB Time limit exceeded
8 Execution timed out 1091 ms 78584 KB Time limit exceeded
9 Execution timed out 1096 ms 78588 KB Time limit exceeded
10 Execution timed out 1088 ms 78840 KB Time limit exceeded
11 Execution timed out 1089 ms 78584 KB Time limit exceeded
12 Execution timed out 1089 ms 78588 KB Time limit exceeded
13 Execution timed out 1094 ms 78712 KB Time limit exceeded
14 Incorrect 680 ms 79960 KB Output isn't correct
15 Execution timed out 1093 ms 78584 KB Time limit exceeded
16 Execution timed out 1103 ms 78584 KB Time limit exceeded
17 Execution timed out 1068 ms 78584 KB Time limit exceeded
18 Execution timed out 1055 ms 78584 KB Time limit exceeded
19 Execution timed out 1101 ms 78584 KB Time limit exceeded
20 Execution timed out 1053 ms 78584 KB Time limit exceeded
21 Execution timed out 1043 ms 78584 KB Time limit exceeded
22 Execution timed out 1059 ms 78584 KB Time limit exceeded
23 Execution timed out 1055 ms 78672 KB Time limit exceeded
24 Execution timed out 1070 ms 78584 KB Time limit exceeded
25 Execution timed out 1105 ms 78584 KB Time limit exceeded
26 Execution timed out 1076 ms 78584 KB Time limit exceeded
27 Execution timed out 1086 ms 78584 KB Time limit exceeded
28 Execution timed out 1080 ms 78584 KB Time limit exceeded
29 Execution timed out 1063 ms 78584 KB Time limit exceeded
30 Execution timed out 1050 ms 78584 KB Time limit exceeded
31 Execution timed out 1101 ms 78584 KB Time limit exceeded
32 Execution timed out 1094 ms 78588 KB Time limit exceeded
33 Execution timed out 1096 ms 78588 KB Time limit exceeded
34 Execution timed out 1102 ms 78584 KB Time limit exceeded
35 Execution timed out 1094 ms 78584 KB Time limit exceeded
36 Execution timed out 1051 ms 78584 KB Time limit exceeded
37 Execution timed out 1098 ms 78584 KB Time limit exceeded
38 Execution timed out 1095 ms 78712 KB Time limit exceeded
39 Execution timed out 1044 ms 78584 KB Time limit exceeded
40 Execution timed out 1065 ms 78584 KB Time limit exceeded
41 Execution timed out 1101 ms 78584 KB Time limit exceeded
42 Execution timed out 1056 ms 78584 KB Time limit exceeded