oj.uz

Submission #155731

# Submission time Handle Problem Language Result Execution time Memory
155731 2019-09-30T07:06:38 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
28.5714 / 100
 1000 ms 158056 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] = inf;
    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] = min(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));
        int num = i;
        while(1) {
            if(num % p[num] != 0) break;
            update(i + p[num] - 1, dp[i] + 1);
            int y = p[num];
            while(num % y == 0)
                num /= y;
        }
    }
    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
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 117880 KB Output is correct
2 Execution timed out 1097 ms 117752 KB Time limit exceeded
3 Correct 935 ms 117864 KB Output is correct
4 Correct 497 ms 117820 KB Output is correct
5 Correct 721 ms 117840 KB Output is correct
6 Correct 604 ms 117816 KB Output is correct
7 Correct 996 ms 117880 KB Output is correct
8 Execution timed out 1082 ms 117796 KB Time limit exceeded
9 Execution timed out 1093 ms 117880 KB Time limit exceeded
10 Execution timed out 1093 ms 117752 KB Time limit exceeded
11 Execution timed out 1064 ms 117784 KB Time limit exceeded
12 Correct 479 ms 117808 KB Output is correct
13 Execution timed out 1093 ms 117816 KB Time limit exceeded
14 Execution timed out 1096 ms 117724 KB Time limit exceeded
15 Execution timed out 1090 ms 117756 KB Time limit exceeded
16 Execution timed out 1083 ms 117752 KB Time limit exceeded
17 Correct 700 ms 117880 KB Output is correct
18 Correct 495 ms 117884 KB Output is correct

Subtask #2
10.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 121948 KB Output is correct
2 Correct 788 ms 157944 KB Output is correct
3 Execution timed out 1081 ms 118808 KB Time limit exceeded
4 Correct 933 ms 118264 KB Output is correct
5 Execution timed out 1058 ms 119052 KB Time limit exceeded
6 Correct 943 ms 118232 KB Output is correct
7 Correct 637 ms 121944 KB Output is correct
8 Correct 808 ms 117844 KB Output is correct
9 Execution timed out 1071 ms 119088 KB Time limit exceeded
10 Execution timed out 1085 ms 118680 KB Time limit exceeded
11 Execution timed out 1093 ms 118216 KB Time limit exceeded
12 Execution timed out 1098 ms 117980 KB Time limit exceeded
13 Correct 684 ms 120184 KB Output is correct
14 Correct 869 ms 118264 KB Output is correct
15 Execution timed out 1085 ms 118648 KB Time limit exceeded
16 Correct 792 ms 158056 KB Output is correct
17 Execution timed out 1092 ms 117880 KB Time limit exceeded
18 Execution timed out 1083 ms 119880 KB Time limit exceeded

Subtask #3
8.57142857143 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 118776 KB Time limit exceeded
2 Execution timed out 1088 ms 118460 KB Time limit exceeded
3 Execution timed out 1090 ms 118392 KB Time limit exceeded
4 Execution timed out 1083 ms 117920 KB Time limit exceeded
5 Incorrect 810 ms 135452 KB Output isn't correct
6 Execution timed out 1073 ms 117916 KB Time limit exceeded
7 Execution timed out 1097 ms 120056 KB Time limit exceeded
8 Execution timed out 1098 ms 118748 KB Time limit exceeded
9 Execution timed out 1094 ms 118776 KB Time limit exceeded
10 Execution timed out 1100 ms 117880 KB Time limit exceeded
11 Execution timed out 1088 ms 118008 KB Time limit exceeded
12 Execution timed out 1090 ms 117916 KB Time limit exceeded
13 Execution timed out 1090 ms 118136 KB Time limit exceeded
14 Execution timed out 1072 ms 117768 KB Time limit exceeded
15 Execution timed out 1077 ms 117884 KB Time limit exceeded
16 Execution timed out 1080 ms 117880 KB Time limit exceeded
17 Execution timed out 1093 ms 118592 KB Time limit exceeded
18 Execution timed out 1084 ms 118528 KB Time limit exceeded
19 Incorrect 858 ms 121068 KB Output isn't correct
20 Execution timed out 1082 ms 118648 KB Time limit exceeded
21 Execution timed out 1086 ms 117732 KB Time limit exceeded
22 Execution timed out 1075 ms 119176 KB Time limit exceeded
23 Correct 799 ms 123000 KB Output is correct
24 Correct 679 ms 118504 KB Output is correct
25 Execution timed out 1083 ms 117980 KB Time limit exceeded
26 Execution timed out 1075 ms 117908 KB Time limit exceeded
27 Execution timed out 1080 ms 119160 KB Time limit exceeded
28 Incorrect 809 ms 118620 KB Output isn't correct
29 Execution timed out 1095 ms 119260 KB Time limit exceeded
30 Execution timed out 1065 ms 118788 KB Time limit exceeded
31 Correct 888 ms 119612 KB Output is correct
32 Correct 996 ms 118520 KB Output is correct
33 Correct 575 ms 118904 KB Output is correct
34 Execution timed out 1081 ms 120056 KB Time limit exceeded
35 Incorrect 842 ms 118568 KB Output isn't correct
36 Execution timed out 1055 ms 119416 KB Time limit exceeded
37 Incorrect 813 ms 135416 KB Output isn't correct
38 Execution timed out 1063 ms 118076 KB Time limit exceeded
39 Correct 713 ms 118580 KB Output is correct
40 Execution timed out 1073 ms 118004 KB Time limit exceeded
41 Execution timed out 1083 ms 121072 KB Time limit exceeded
42 Execution timed out 1084 ms 117844 KB Time limit exceeded