oj.uz

Submission #155732

# Submission time Handle Problem Language Result Execution time Memory
155732 2019-09-30T07:13:00 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
46.8254 / 100
 1000 ms 157940 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int mod = 1e9 + 7;

const int inf = 1e9;

int add(int x, int y) {
    return (1ll * x + 1ll * y) % mod;
}

int del(int x, int y) {
    return ((1ll * x - 1ll * y) % mod + mod) % mod;
}

int mul(int x, int y) {
    return (1ll * x * 1ll * y) % mod;
}

const int N = 1e7 + 5;

int dp[2 * N], p[N];
bool used[N];
int bit[2 * N];

void update(int x, int val) {
    while(x > 0) {
        bit[x] = min(bit[x], val);
        x -= x & (-x);
    }
}

int get(int x) {
    if(x == 0) return 0;
    int val = inf;
    while(x < N) {
        val = min(val, bit[x]);
        x += x & (-x);
    }
    return val;
}

int m, q;

int main() {
    cin.tie(0), ios_base::sync_with_stdio(0);
    cin >> m >> q;
    for(int i = 0; i < N; i++)
        p[i] = 0;
    for(int i = 1; i <= N - 5; i++)
        bit[i] = dp[i] = inf;
    for(int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        if(used[x]) continue;
        used[x] = 1;
        dp[x - 1] = 1;
        for(int l = 0; l < N; l++) {
            if(x * l >= N) break;
            p[x * l] = max(p[x * l], x);
        }
    }
    for(int i = N - 6; i >= 0; i--)
        dp[i] = min(dp[i + 1], dp[i]);
    for(int i = 1; i <= N - 5; i++) {
        dp[i] = min(dp[i], get(i));
        if(p[i] == 0 || i % p[i] != 0) continue;
        //cout << i << " " << p[i] << " " << dp[i] << "\n";
        update(i + p[i] - 1, dp[i] + 1);
    }
    for(int i = 1; i <= q; i++) {
        int x;
        cin >> x;
        if(dp[x] == inf)
            cout << "oo\n";
        else
            cout << dp[x] << "\n";
    }
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 117816 KB Output is correct
2 Correct 763 ms 117820 KB Output is correct
3 Correct 713 ms 117940 KB Output is correct
4 Correct 446 ms 117880 KB Output is correct
5 Correct 588 ms 117816 KB Output is correct
6 Correct 539 ms 117816 KB Output is correct
7 Correct 700 ms 117812 KB Output is correct
8 Correct 763 ms 117812 KB Output is correct
9 Correct 826 ms 117808 KB Output is correct
10 Correct 860 ms 117880 KB Output is correct
11 Correct 809 ms 117848 KB Output is correct
12 Correct 421 ms 117808 KB Output is correct
13 Correct 995 ms 117828 KB Output is correct
14 Correct 999 ms 117856 KB Output is correct
15 Correct 762 ms 117928 KB Output is correct
16 Correct 862 ms 117880 KB Output is correct
17 Correct 593 ms 117900 KB Output is correct
18 Correct 444 ms 117824 KB Output is correct

Subtask #2
11.1111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 122028 KB Output is correct
2 Correct 733 ms 157940 KB Output is correct
3 Execution timed out 1086 ms 118776 KB Time limit exceeded
4 Correct 707 ms 118308 KB Output is correct
5 Execution timed out 1031 ms 123952 KB Time limit exceeded
6 Correct 708 ms 118152 KB Output is correct
7 Correct 566 ms 121880 KB Output is correct
8 Correct 667 ms 117844 KB Output is correct
9 Execution timed out 1083 ms 122932 KB Time limit exceeded
10 Execution timed out 1088 ms 118824 KB Time limit exceeded
11 Execution timed out 1089 ms 118264 KB Time limit exceeded
12 Correct 850 ms 118104 KB Output is correct
13 Correct 589 ms 120168 KB Output is correct
14 Correct 738 ms 118264 KB Output is correct
15 Execution timed out 1056 ms 118596 KB Time limit exceeded
16 Correct 736 ms 157936 KB Output is correct
17 Execution timed out 1057 ms 117808 KB Time limit exceeded
18 Execution timed out 1085 ms 125008 KB Time limit exceeded

Subtask #3
15.7142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 122060 KB Time limit exceeded
2 Execution timed out 1083 ms 118484 KB Time limit exceeded
3 Execution timed out 1073 ms 118584 KB Time limit exceeded
4 Incorrect 897 ms 118592 KB Output isn't correct
5 Incorrect 784 ms 135368 KB Output isn't correct
6 Execution timed out 1046 ms 118612 KB Time limit exceeded
7 Execution timed out 1043 ms 125872 KB Time limit exceeded
8 Execution timed out 1074 ms 122232 KB Time limit exceeded
9 Execution timed out 1084 ms 121616 KB Time limit exceeded
10 Correct 908 ms 118328 KB Output is correct
11 Correct 843 ms 118392 KB Output is correct
12 Correct 989 ms 118364 KB Output is correct
13 Execution timed out 1091 ms 119516 KB Time limit exceeded
14 Correct 893 ms 118392 KB Output is correct
15 Execution timed out 1032 ms 118280 KB Time limit exceeded
16 Execution timed out 1070 ms 117956 KB Time limit exceeded
17 Execution timed out 1073 ms 121692 KB Time limit exceeded
18 Execution timed out 1085 ms 118572 KB Time limit exceeded
19 Incorrect 660 ms 121100 KB Output isn't correct
20 Execution timed out 1098 ms 118392 KB Time limit exceeded
21 Incorrect 958 ms 118364 KB Output isn't correct
22 Execution timed out 1080 ms 119228 KB Time limit exceeded
23 Correct 762 ms 122880 KB Output is correct
24 Correct 609 ms 118552 KB Output is correct
25 Correct 929 ms 118440 KB Output is correct
26 Incorrect 909 ms 118492 KB Output isn't correct
27 Execution timed out 1086 ms 119192 KB Time limit exceeded
28 Incorrect 663 ms 118648 KB Output isn't correct
29 Execution timed out 1088 ms 119372 KB Time limit exceeded
30 Execution timed out 1073 ms 120860 KB Time limit exceeded
31 Correct 720 ms 119412 KB Output is correct
32 Correct 775 ms 118480 KB Output is correct
33 Correct 507 ms 119032 KB Output is correct
34 Execution timed out 1081 ms 127740 KB Time limit exceeded
35 Incorrect 688 ms 118688 KB Output isn't correct
36 Execution timed out 1077 ms 119332 KB Time limit exceeded
37 Incorrect 783 ms 135416 KB Output isn't correct
38 Execution timed out 1061 ms 118904 KB Time limit exceeded
39 Correct 631 ms 118648 KB Output is correct
40 Execution timed out 1050 ms 118948 KB Time limit exceeded
41 Execution timed out 1055 ms 133720 KB Time limit exceeded
42 Execution timed out 1078 ms 118300 KB Time limit exceeded