oj.uz

Submission #757322

# Submission time Handle Problem Language Result Execution time Memory
757322 2023-06-13T05:18:37 Z The_Samurai Brunhilda’s Birthday (BOI13_brunhilda) C++17
50.9524 / 100
 1000 ms 79848 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() {
    clock_t startTime = clock();
//    int N = 1e4;
//    vector<int> g(N + 1);
//    vector<int> dp(N + 1, (int)1e9);
//    primes = {5, 11, 19};
//    dp[0] = 0;
//    for (int i = 1; i <= N; i++) {
//        for (int p: primes) {
//            dp[i] = min(dp[i], dp[i - i % p] + 1);
//        }
//    }
//    for (int i = 1; i <= 100; i++) {
//        cout << i << " -> " << dp[i] << endl;
//    }
    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;
    }
    reverse(primes.begin(), primes.end());
    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:17:13: warning: unused variable 'startTime' [-Wunused-variable]
   17 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 78580 KB Output is correct
2 Correct 131 ms 78576 KB Output is correct
3 Correct 79 ms 78656 KB Output is correct
4 Correct 100 ms 78548 KB Output is correct
5 Correct 104 ms 78584 KB Output is correct
6 Correct 69 ms 78580 KB Output is correct
7 Correct 81 ms 78572 KB Output is correct
8 Correct 84 ms 78576 KB Output is correct
9 Correct 100 ms 78576 KB Output is correct
10 Correct 142 ms 78580 KB Output is correct
11 Correct 140 ms 78548 KB Output is correct
12 Correct 85 ms 78572 KB Output is correct
13 Correct 236 ms 78584 KB Output is correct
14 Correct 220 ms 78540 KB Output is correct
15 Correct 129 ms 78568 KB Output is correct
16 Correct 136 ms 78688 KB Output is correct
17 Correct 119 ms 78652 KB Output is correct
18 Correct 88 ms 78540 KB Output is correct

Subtask #2
6.66666666667 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 78608 KB Time limit exceeded
2 Execution timed out 1084 ms 79564 KB Time limit exceeded
3 Execution timed out 1071 ms 79296 KB Time limit exceeded
4 Correct 454 ms 78512 KB Output is correct
5 Execution timed out 1073 ms 79004 KB Time limit exceeded
6 Correct 184 ms 78584 KB Output is correct
7 Execution timed out 1091 ms 78688 KB Time limit exceeded
8 Correct 167 ms 78580 KB Output is correct
9 Execution timed out 1086 ms 79324 KB Time limit exceeded
10 Execution timed out 1069 ms 79204 KB Time limit exceeded
11 Execution timed out 1079 ms 78920 KB Time limit exceeded
12 Correct 265 ms 78584 KB Output is correct
13 Execution timed out 1064 ms 78600 KB Time limit exceeded
14 Correct 432 ms 78540 KB Output is correct
15 Execution timed out 1081 ms 79008 KB Time limit exceeded
16 Execution timed out 1086 ms 79516 KB Time limit exceeded
17 Correct 230 ms 78600 KB Output is correct
18 Execution timed out 1095 ms 79664 KB Time limit exceeded

Subtask #3
24.2857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 79248 KB Time limit exceeded
2 Execution timed out 1038 ms 79148 KB Time limit exceeded
3 Execution timed out 1079 ms 79140 KB Time limit exceeded
4 Correct 633 ms 79456 KB Output is correct
5 Execution timed out 1083 ms 79716 KB Time limit exceeded
6 Execution timed out 1082 ms 78796 KB Time limit exceeded
7 Execution timed out 1084 ms 79792 KB Time limit exceeded
8 Execution timed out 1077 ms 79136 KB Time limit exceeded
9 Execution timed out 1070 ms 79240 KB Time limit exceeded
10 Correct 721 ms 78700 KB Output is correct
11 Correct 534 ms 78828 KB Output is correct
12 Correct 707 ms 78828 KB Output is correct
13 Execution timed out 1078 ms 79044 KB Time limit exceeded
14 Correct 300 ms 79772 KB Output is correct
15 Correct 690 ms 78828 KB Output is correct
16 Correct 775 ms 78876 KB Output is correct
17 Execution timed out 1089 ms 79092 KB Time limit exceeded
18 Execution timed out 1056 ms 79268 KB Time limit exceeded
19 Execution timed out 1085 ms 78640 KB Time limit exceeded
20 Execution timed out 1080 ms 79204 KB Time limit exceeded
21 Correct 304 ms 79848 KB Output is correct
22 Execution timed out 1090 ms 79708 KB Time limit exceeded
23 Execution timed out 1056 ms 78924 KB Time limit exceeded
24 Correct 309 ms 79532 KB Output is correct
25 Correct 459 ms 79544 KB Output is correct
26 Correct 575 ms 79620 KB Output is correct
27 Execution timed out 1078 ms 79716 KB Time limit exceeded
28 Correct 266 ms 79564 KB Output is correct
29 Execution timed out 1096 ms 79724 KB Time limit exceeded
30 Execution timed out 1085 ms 79436 KB Time limit exceeded
31 Execution timed out 1057 ms 79336 KB Time limit exceeded
32 Correct 466 ms 79648 KB Output is correct
33 Correct 379 ms 79496 KB Output is correct
34 Execution timed out 1029 ms 79820 KB Time limit exceeded
35 Correct 298 ms 79776 KB Output is correct
36 Execution timed out 1092 ms 79780 KB Time limit exceeded
37 Execution timed out 1084 ms 79820 KB Time limit exceeded
38 Execution timed out 1048 ms 78796 KB Time limit exceeded
39 Correct 468 ms 79616 KB Output is correct
40 Execution timed out 1078 ms 78796 KB Time limit exceeded
41 Execution timed out 1087 ms 79716 KB Time limit exceeded
42 Correct 394 ms 79764 KB Output is correct