oj.uz

Submission #493692

# Submission time Handle Problem Language Result Execution time Memory
493692 2021-12-12T15:21:44 Z SangTin Brunhilda’s Birthday (BOI13_brunhilda) C++14
40 / 100
 1000 ms 53588 KB 
#include <bits/stdc++.h>

using namespace std;

#define name "TRACKS"
#define endl '\n'
#define ednl endl
#define long long long
#define memset(a, x) memset(a, (x), sizeof(a));
#define inoutf freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define IN(a, b, c) (a <= b && b <= c)

template<typename T, typename U> inline bool amin(T &x, U y) { if(y >= x) return 0; x = y; return 1;}
template<typename T, typename U> inline bool amax(T &x, U y) { if(x >= y) return 0; x = y; return 1;}
template<typename T> inline void read(T& x){
    bool Neg = false;
    char c;
    for (c = getchar(); c < '0' | c > '9'; c = getchar())
        if (c == '-') Neg = !Neg;
    x = c - '0';
    for (c = getchar(); c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    if (Neg) x = -x;
}

const int M = 1e5 + 83, N = 1e7 + 83;
int p[M], spf[N], m;
bool isPrime[N];
vector <int> Prime;

void Sieve(){
    memset(isPrime, 1);
    memset(spf, 0x3f);
    for (int i = 2; i < N; ++i){
        if (isPrime[i]){
            Prime.push_back(i);
            spf[i] = i;
        }
        for (int j = 0; j < Prime.size() && 1ll * i * Prime[j] < N && Prime[j] <= spf[i]; ++j){
            isPrime[i * Prime[j]] = 0;
            spf[i * Prime[j]] = Prime[j];
        }
    }
}

int cal(int n){
    if (!n) return 0;
    int cur = m, tmp = n, Max = 0;
    for (int i = 1; i <= m; ++i){
        if (tmp % p[i]) amax(Max, tmp % p[i]);
    }
    if (!Max) return -1;
//    cout << n << ' ' << Max << '\n';
    int add = cal(n - Max);
    if (add == -1) return -1;
    return add + 1;
}

int Solve(){
    Sieve();
    int q; cin >> m >> q;
    for (int i = 1; i <= m; ++i) cin >> p[i];
    sort(p + 1, p + m + 1);
    while (q--){
        int n; cin >> n;
        int tmp = cal(n);
        if (tmp == -1) cout << "oo\n";
        else cout << tmp << endl;
    }

    return 0;
}

int main(){
    fastio;

    int t = 1;
//    cin >> t;
    while (t--){
        Solve();
    }

    return 0;
}

Compilation message

brunhilda.cpp: In function 'void Sieve()':
brunhilda.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int j = 0; j < Prime.size() && 1ll * i * Prime[j] < N && Prime[j] <= spf[i]; ++j){
      |                         ~~^~~~~~~~~~~~~~
brunhilda.cpp: In function 'int cal(int)':
brunhilda.cpp:49:9: warning: unused variable 'cur' [-Wunused-variable]
   49 |     int cur = m, tmp = n, Max = 0;
      |         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 53432 KB Output is correct
2 Correct 131 ms 53432 KB Output is correct
3 Correct 121 ms 53444 KB Output is correct
4 Correct 137 ms 53376 KB Output is correct
5 Correct 122 ms 53388 KB Output is correct
6 Correct 127 ms 53572 KB Output is correct
7 Correct 119 ms 53408 KB Output is correct
8 Correct 141 ms 53420 KB Output is correct
9 Correct 134 ms 53456 KB Output is correct
10 Correct 124 ms 53444 KB Output is correct
11 Correct 130 ms 53356 KB Output is correct
12 Correct 118 ms 53464 KB Output is correct
13 Correct 145 ms 53408 KB Output is correct
14 Correct 167 ms 53412 KB Output is correct
15 Correct 120 ms 53464 KB Output is correct
16 Correct 122 ms 53432 KB Output is correct
17 Correct 152 ms 53432 KB Output is correct
18 Correct 131 ms 53460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 53440 KB Output is correct
2 Correct 135 ms 53392 KB Output is correct
3 Correct 130 ms 53376 KB Output is correct
4 Correct 130 ms 53408 KB Output is correct
5 Correct 143 ms 53544 KB Output is correct
6 Correct 123 ms 53436 KB Output is correct
7 Correct 127 ms 53360 KB Output is correct
8 Correct 150 ms 53468 KB Output is correct
9 Correct 144 ms 53432 KB Output is correct
10 Correct 134 ms 53412 KB Output is correct
11 Correct 132 ms 53480 KB Output is correct
12 Correct 128 ms 53388 KB Output is correct
13 Correct 146 ms 53480 KB Output is correct
14 Correct 131 ms 53436 KB Output is correct
15 Correct 137 ms 53376 KB Output is correct
16 Correct 136 ms 53424 KB Output is correct
17 Correct 148 ms 53464 KB Output is correct
18 Correct 140 ms 53464 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 53548 KB Time limit exceeded
2 Execution timed out 1087 ms 53452 KB Time limit exceeded
3 Execution timed out 1077 ms 53456 KB Time limit exceeded
4 Execution timed out 1088 ms 53428 KB Time limit exceeded
5 Execution timed out 1096 ms 53428 KB Time limit exceeded
6 Execution timed out 1096 ms 53436 KB Time limit exceeded
7 Execution timed out 1088 ms 53364 KB Time limit exceeded
8 Execution timed out 1088 ms 53540 KB Time limit exceeded
9 Execution timed out 1082 ms 53432 KB Time limit exceeded
10 Execution timed out 1094 ms 53364 KB Time limit exceeded
11 Execution timed out 1085 ms 53424 KB Time limit exceeded
12 Execution timed out 1090 ms 53432 KB Time limit exceeded
13 Execution timed out 1093 ms 53432 KB Time limit exceeded
14 Execution timed out 1078 ms 53460 KB Time limit exceeded
15 Execution timed out 1091 ms 53432 KB Time limit exceeded
16 Execution timed out 1085 ms 53444 KB Time limit exceeded
17 Execution timed out 1085 ms 53412 KB Time limit exceeded
18 Execution timed out 1083 ms 53388 KB Time limit exceeded
19 Execution timed out 1090 ms 53588 KB Time limit exceeded
20 Execution timed out 1091 ms 53436 KB Time limit exceeded
21 Execution timed out 1066 ms 53472 KB Time limit exceeded
22 Execution timed out 1081 ms 53424 KB Time limit exceeded
23 Execution timed out 1063 ms 53388 KB Time limit exceeded
24 Execution timed out 1077 ms 53360 KB Time limit exceeded
25 Execution timed out 1059 ms 53368 KB Time limit exceeded
26 Execution timed out 1073 ms 53376 KB Time limit exceeded
27 Execution timed out 1093 ms 53428 KB Time limit exceeded
28 Execution timed out 1093 ms 53472 KB Time limit exceeded
29 Execution timed out 1084 ms 53420 KB Time limit exceeded
30 Execution timed out 1081 ms 53464 KB Time limit exceeded
31 Execution timed out 1092 ms 53400 KB Time limit exceeded
32 Execution timed out 1098 ms 53432 KB Time limit exceeded
33 Execution timed out 1093 ms 53376 KB Time limit exceeded
34 Execution timed out 1099 ms 53376 KB Time limit exceeded
35 Execution timed out 1097 ms 53460 KB Time limit exceeded
36 Execution timed out 1099 ms 53472 KB Time limit exceeded
37 Execution timed out 1085 ms 53428 KB Time limit exceeded
38 Execution timed out 1096 ms 53472 KB Time limit exceeded
39 Execution timed out 1095 ms 53364 KB Time limit exceeded
40 Execution timed out 1089 ms 53468 KB Time limit exceeded
41 Execution timed out 1085 ms 53408 KB Time limit exceeded
42 Execution timed out 1089 ms 53452 KB Time limit exceeded