oj.uz

Submission #493688

# Submission time Handle Problem Language Result Execution time Memory
493688 2021-12-12T15:13:38 Z SangTin Brunhilda’s Birthday (BOI13_brunhilda) C++14
8.09524 / 100
 1000 ms 53616 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;
    while (cur && tmp % p[cur] == 0){
        while (tmp % p[cur] == 0) tmp /= p[cur];
        --cur;
    }
    if (!cur) return -1;
    int add = cal(n - n % p[cur]);
    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){
      |                         ~~^~~~~~~~~~~~~~

Subtask #1
1.11111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 53396 KB Output isn't correct
2 Incorrect 120 ms 53476 KB Output isn't correct
3 Incorrect 133 ms 53448 KB Output isn't correct
4 Incorrect 136 ms 53444 KB Output isn't correct
5 Incorrect 127 ms 53452 KB Output isn't correct
6 Incorrect 124 ms 53424 KB Output isn't correct
7 Incorrect 138 ms 53560 KB Output isn't correct
8 Incorrect 140 ms 53448 KB Output isn't correct
9 Incorrect 122 ms 53456 KB Output isn't correct
10 Incorrect 128 ms 53440 KB Output isn't correct
11 Incorrect 129 ms 53412 KB Output isn't correct
12 Correct 130 ms 53372 KB Output is correct
13 Incorrect 118 ms 53432 KB Output isn't correct
14 Incorrect 121 ms 53356 KB Output isn't correct
15 Incorrect 120 ms 53444 KB Output isn't correct
16 Incorrect 121 ms 53452 KB Output isn't correct
17 Incorrect 152 ms 53428 KB Output isn't correct
18 Incorrect 122 ms 53392 KB Output isn't correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 53380 KB Output isn't correct
2 Correct 133 ms 53500 KB Output is correct
3 Correct 139 ms 53484 KB Output is correct
4 Incorrect 126 ms 53432 KB Output isn't correct
5 Correct 126 ms 53444 KB Output is correct
6 Incorrect 128 ms 53412 KB Output isn't correct
7 Incorrect 138 ms 53400 KB Output isn't correct
8 Incorrect 131 ms 53400 KB Output isn't correct
9 Incorrect 132 ms 53432 KB Output isn't correct
10 Correct 131 ms 53456 KB Output is correct
11 Incorrect 125 ms 53440 KB Output isn't correct
12 Incorrect 142 ms 53552 KB Output isn't correct
13 Incorrect 134 ms 53424 KB Output isn't correct
14 Incorrect 123 ms 53408 KB Output isn't correct
15 Incorrect 133 ms 53372 KB Output isn't correct
16 Correct 147 ms 53432 KB Output is correct
17 Incorrect 138 ms 53408 KB Output isn't correct
18 Incorrect 129 ms 53496 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 53380 KB Output isn't correct
2 Incorrect 155 ms 53556 KB Output isn't correct
3 Incorrect 167 ms 53428 KB Output isn't correct
4 Incorrect 305 ms 53420 KB Output isn't correct
5 Incorrect 157 ms 53400 KB Output isn't correct
6 Incorrect 299 ms 53472 KB Output isn't correct
7 Incorrect 139 ms 53372 KB Output isn't correct
8 Incorrect 152 ms 53420 KB Output isn't correct
9 Incorrect 157 ms 53412 KB Output isn't correct
10 Incorrect 153 ms 53364 KB Output isn't correct
11 Incorrect 169 ms 53436 KB Output isn't correct
12 Incorrect 170 ms 53556 KB Output isn't correct
13 Incorrect 186 ms 53392 KB Output isn't correct
14 Execution timed out 1090 ms 53480 KB Time limit exceeded
15 Incorrect 179 ms 53456 KB Output isn't correct
16 Incorrect 181 ms 53416 KB Output isn't correct
17 Incorrect 137 ms 53436 KB Output isn't correct
18 Incorrect 147 ms 53444 KB Output isn't correct
19 Incorrect 132 ms 53432 KB Output isn't correct
20 Incorrect 153 ms 53464 KB Output isn't correct
21 Execution timed out 1093 ms 53360 KB Time limit exceeded
22 Incorrect 177 ms 53516 KB Output isn't correct
23 Incorrect 181 ms 53504 KB Output isn't correct
24 Incorrect 324 ms 53388 KB Output isn't correct
25 Incorrect 526 ms 53444 KB Output isn't correct
26 Incorrect 334 ms 53388 KB Output isn't correct
27 Incorrect 146 ms 53428 KB Output isn't correct
28 Incorrect 362 ms 53532 KB Output isn't correct
29 Incorrect 174 ms 53364 KB Output isn't correct
30 Incorrect 166 ms 53372 KB Output isn't correct
31 Incorrect 208 ms 53444 KB Output isn't correct
32 Incorrect 353 ms 53504 KB Output isn't correct
33 Incorrect 235 ms 53488 KB Output isn't correct
34 Incorrect 145 ms 53432 KB Output isn't correct
35 Incorrect 379 ms 53440 KB Output isn't correct
36 Incorrect 166 ms 53436 KB Output isn't correct
37 Incorrect 179 ms 53460 KB Output isn't correct
38 Incorrect 286 ms 53616 KB Output isn't correct
39 Incorrect 314 ms 53432 KB Output isn't correct
40 Incorrect 248 ms 53444 KB Output isn't correct
41 Correct 139 ms 53440 KB Output is correct
42 Incorrect 907 ms 53456 KB Output isn't correct