oj.uz

Submission #757326

# Submission time Handle Problem Language Result Execution time Memory
757326 2023-06-13T05:21:24 Z The_Samurai Brunhilda’s Birthday (BOI13_brunhilda) C++17
52.381 / 100
 1000 ms 79388 KB 
#include "bits/stdc++.h"

using namespace std;

bool isPrime(int n) {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return n > 1;
}

int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    clock_t startTime = clock();
    int n, q, N = 1e7;
    cin >> n >> q;
    vector<int> primes(n), g(N + 1), dp(N + 1, INF);
    iota(g.begin(), g.end(), 0);
    for (int &p: primes) {
        cin >> p;
    }
    sort(primes.rbegin(), primes.rend());
    for (int i = 0; i < n; i++) {
        int p = primes[i];
        for (int j = 0; j <= N; j += p) {
            for (int k = min(N, j + p - 1); k > j and j < g[k]; k--) {
                g[k] = j;
            }
        }
    }
    dp[0] = 0;
    for (int i = 1; i <= N; i++) {
        dp[i] = dp[g[i]] + 1;
    }
    while (q--) {
        int x;
        cin >> x;
        if (dp[x] >= INF) {
            cout << "oo\n";
        } else {
            cout << dp[x] << '\n';
        }
    }

#ifdef sunnitov
    cerr << "\nTime: " << (int)((double)(clock() - startTime) / CLOCKS_PER_SEC * 1000);
#endif
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:18:13: warning: unused variable 'startTime' [-Wunused-variable]
   18 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 78544 KB Output is correct
2 Correct 130 ms 78500 KB Output is correct
3 Correct 73 ms 78548 KB Output is correct
4 Correct 74 ms 78540 KB Output is correct
5 Correct 101 ms 78548 KB Output is correct
6 Correct 70 ms 78500 KB Output is correct
7 Correct 78 ms 78540 KB Output is correct
8 Correct 85 ms 78492 KB Output is correct
9 Correct 93 ms 78592 KB Output is correct
10 Correct 131 ms 78592 KB Output is correct
11 Correct 125 ms 78596 KB Output is correct
12 Correct 82 ms 78480 KB Output is correct
13 Correct 225 ms 78604 KB Output is correct
14 Correct 228 ms 78596 KB Output is correct
15 Correct 118 ms 78592 KB Output is correct
16 Correct 126 ms 78600 KB Output is correct
17 Correct 111 ms 78588 KB Output is correct
18 Correct 73 ms 78544 KB Output is correct

Subtask #2
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 78544 KB Time limit exceeded
2 Execution timed out 1089 ms 78932 KB Time limit exceeded
3 Execution timed out 1084 ms 78864 KB Time limit exceeded
4 Correct 486 ms 78604 KB Output is correct
5 Execution timed out 1074 ms 78804 KB Time limit exceeded
6 Correct 174 ms 78632 KB Output is correct
7 Execution timed out 1087 ms 78588 KB Time limit exceeded
8 Correct 144 ms 78588 KB Output is correct
9 Execution timed out 1092 ms 78924 KB Time limit exceeded
10 Execution timed out 1080 ms 78836 KB Time limit exceeded
11 Execution timed out 1068 ms 78748 KB Time limit exceeded
12 Correct 242 ms 78604 KB Output is correct
13 Execution timed out 1022 ms 78604 KB Time limit exceeded
14 Correct 464 ms 78660 KB Output is correct
15 Execution timed out 1088 ms 78760 KB Time limit exceeded
16 Execution timed out 1055 ms 78924 KB Time limit exceeded
17 Correct 249 ms 78540 KB Output is correct
18 Execution timed out 1089 ms 78912 KB Time limit exceeded

Subtask #3
25.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1065 ms 78708 KB Time limit exceeded
2 Execution timed out 1069 ms 78712 KB Time limit exceeded
3 Execution timed out 1078 ms 78664 KB Time limit exceeded
4 Correct 451 ms 78968 KB Output is correct
5 Execution timed out 1075 ms 78948 KB Time limit exceeded
6 Execution timed out 1058 ms 79388 KB Time limit exceeded
7 Execution timed out 1080 ms 79000 KB Time limit exceeded
8 Execution timed out 1074 ms 78668 KB Time limit exceeded
9 Execution timed out 1075 ms 78804 KB Time limit exceeded
10 Correct 688 ms 78616 KB Output is correct
11 Correct 501 ms 78656 KB Output is correct
12 Correct 692 ms 78612 KB Output is correct
13 Execution timed out 1062 ms 78724 KB Time limit exceeded
14 Correct 176 ms 79120 KB Output is correct
15 Correct 609 ms 78616 KB Output is correct
16 Correct 838 ms 78668 KB Output is correct
17 Execution timed out 1073 ms 78684 KB Time limit exceeded
18 Execution timed out 1065 ms 78804 KB Time limit exceeded
19 Execution timed out 1077 ms 78548 KB Time limit exceeded
20 Execution timed out 1085 ms 78668 KB Time limit exceeded
21 Correct 159 ms 79112 KB Output is correct
22 Execution timed out 1087 ms 78936 KB Time limit exceeded
23 Execution timed out 1076 ms 78676 KB Time limit exceeded
24 Correct 177 ms 78796 KB Output is correct
25 Correct 393 ms 78860 KB Output is correct
26 Correct 447 ms 78860 KB Output is correct
27 Execution timed out 1070 ms 78884 KB Time limit exceeded
28 Correct 121 ms 78868 KB Output is correct
29 Execution timed out 1091 ms 78976 KB Time limit exceeded
30 Execution timed out 1079 ms 78796 KB Time limit exceeded
31 Correct 995 ms 78796 KB Output is correct
32 Correct 373 ms 78948 KB Output is correct
33 Correct 290 ms 78828 KB Output is correct
34 Execution timed out 1043 ms 78944 KB Time limit exceeded
35 Correct 152 ms 78820 KB Output is correct
36 Execution timed out 1090 ms 78932 KB Time limit exceeded
37 Execution timed out 1089 ms 78972 KB Time limit exceeded
38 Execution timed out 1082 ms 78524 KB Time limit exceeded
39 Correct 360 ms 78924 KB Output is correct
40 Execution timed out 1089 ms 78556 KB Time limit exceeded
41 Execution timed out 1089 ms 78872 KB Time limit exceeded
42 Correct 253 ms 79004 KB Output is correct