oj.uz

Submission #757435

# Submission time Handle Problem Language Result Execution time Memory
757435 2023-06-13T07:36:30 Z dxz05 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 1000 ms 736 KB 
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
 
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)
#define MP make_pair
//#define endl '\n'
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
 
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 1e4 + 2;
 
int dp[N];
 
void solve(){
    int m, q;
    cin >> m >> q;
 
    vector<int> primes(m);
    for (int i = 0; i < m; i++) cin >> primes[i];
 
    fill(dp + 1, dp + N, 1e9);
 
    dp[0] = 0;
    for (int i = 1; i < N; i++){
        for (int p : primes){
            dp[i] = min(dp[i], dp[i / p * p] + 1);
        }
    }
 
    for (int i = 1; i < N; i++){
        assert(dp[i] >= dp[i - 1] && dp[i] <= dp[i - 1] + 1 || dp[i] == 1e9);
    }
 
    while (q--){
        int i;
        cin >> i;
        if (dp[i] != 1e9){
            cout << dp[i] << "\n";
        } else {
            cout << "oo\n";
        }
    }
 
}
 
int main(){
    clock_t startTime = clock();
    ios_base::sync_with_stdio(false);
 
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
 
    int test_cases = 1;
//    cin >> test_cases;
 
    for (int test = 1; test <= test_cases; test++){
        // cout << (solve() ? "YES" : "NO") << endl;
        solve();
    }
 
#ifdef LOCAL
    cerr << "Time: " << int((double) (clock() - startTime) / CLOCKS_PER_SEC * 1000) << " ms" << endl;
#endif
 
    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from brunhilda.cpp:4:
brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:40:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   40 |         assert(dp[i] >= dp[i - 1] && dp[i] <= dp[i - 1] + 1 || dp[i] == 1e9);
      |                ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
brunhilda.cpp: In function 'int main()':
brunhilda.cpp:56:13: warning: unused variable 'startTime' [-Wunused-variable]
   56 |     clock_t startTime = clock();
      |             ^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 368 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 4 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 6 ms 340 KB Output is correct
13 Correct 54 ms 344 KB Output is correct
14 Correct 69 ms 360 KB Output is correct
15 Correct 3 ms 340 KB Output is correct
16 Correct 5 ms 340 KB Output is correct
17 Correct 23 ms 376 KB Output is correct
18 Correct 19 ms 372 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 616 ms 520 KB Execution killed with signal 11
2 Execution timed out 1084 ms 700 KB Time limit exceeded
3 Execution timed out 1074 ms 596 KB Time limit exceeded
4 Runtime error 152 ms 460 KB Execution killed with signal 11
5 Execution timed out 1070 ms 468 KB Time limit exceeded
6 Runtime error 57 ms 460 KB Execution killed with signal 11
7 Runtime error 576 ms 520 KB Execution killed with signal 11
8 Runtime error 49 ms 476 KB Execution killed with signal 11
9 Execution timed out 1082 ms 620 KB Time limit exceeded
10 Execution timed out 1087 ms 596 KB Time limit exceeded
11 Execution timed out 1084 ms 468 KB Time limit exceeded
12 Runtime error 105 ms 460 KB Execution killed with signal 11
13 Runtime error 151 ms 484 KB Execution killed with signal 11
14 Runtime error 149 ms 484 KB Execution killed with signal 11
15 Execution timed out 1077 ms 468 KB Time limit exceeded
16 Execution timed out 1073 ms 724 KB Time limit exceeded
17 Runtime error 155 ms 460 KB Execution killed with signal 11
18 Execution timed out 1084 ms 724 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 468 KB Time limit exceeded
2 Execution timed out 1084 ms 468 KB Time limit exceeded
3 Execution timed out 1078 ms 468 KB Time limit exceeded
4 Runtime error 161 ms 488 KB Execution killed with signal 11
5 Execution timed out 1091 ms 736 KB Time limit exceeded
6 Runtime error 374 ms 504 KB Execution killed with signal 11
7 Execution timed out 1089 ms 724 KB Time limit exceeded
8 Execution timed out 1076 ms 468 KB Time limit exceeded
9 Execution timed out 1076 ms 468 KB Time limit exceeded
10 Runtime error 281 ms 500 KB Execution killed with signal 11
11 Runtime error 212 ms 488 KB Execution killed with signal 11
12 Runtime error 275 ms 460 KB Execution killed with signal 11
13 Execution timed out 1083 ms 468 KB Time limit exceeded
14 Runtime error 3 ms 468 KB Execution killed with signal 11
15 Runtime error 257 ms 508 KB Execution killed with signal 11
16 Runtime error 327 ms 496 KB Execution killed with signal 11
17 Execution timed out 1086 ms 468 KB Time limit exceeded
18 Execution timed out 1061 ms 468 KB Time limit exceeded
19 Runtime error 239 ms 492 KB Execution killed with signal 11
20 Execution timed out 1082 ms 468 KB Time limit exceeded
21 Runtime error 6 ms 468 KB Execution killed with signal 11
22 Execution timed out 1079 ms 732 KB Time limit exceeded
23 Execution timed out 1067 ms 468 KB Time limit exceeded
24 Runtime error 55 ms 492 KB Execution killed with signal 11
25 Runtime error 137 ms 460 KB Execution killed with signal 11
26 Runtime error 159 ms 496 KB Execution killed with signal 11
27 Execution timed out 1069 ms 724 KB Time limit exceeded
28 Runtime error 48 ms 484 KB Execution killed with signal 11
29 Execution timed out 1088 ms 724 KB Time limit exceeded
30 Execution timed out 1082 ms 596 KB Time limit exceeded
31 Runtime error 206 ms 492 KB Execution killed with signal 11
32 Runtime error 136 ms 496 KB Execution killed with signal 11
33 Runtime error 60 ms 588 KB Execution killed with signal 11
34 Execution timed out 1087 ms 724 KB Time limit exceeded
35 Runtime error 96 ms 476 KB Execution killed with signal 11
36 Execution timed out 1095 ms 692 KB Time limit exceeded
37 Execution timed out 1078 ms 728 KB Time limit exceeded
38 Runtime error 386 ms 504 KB Execution killed with signal 11
39 Runtime error 113 ms 476 KB Execution killed with signal 11
40 Runtime error 437 ms 504 KB Execution killed with signal 11
41 Execution timed out 1087 ms 728 KB Time limit exceeded
42 Runtime error 146 ms 588 KB Execution killed with signal 11