oj.uz

Submission #155745

# Submission time Handle Problem Language Result Execution time Memory
155745 2019-09-30T08:24:12 Z Flying_dragon_02 Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 1000 ms 149208 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[N], p[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 < 2 * N) {
        val = min(val, bit[x]);
        x += x & (-x);
    }
    return val;
}
 
int m, q;
 
int main() {
    scanf("%d%d", &m, &q);
    for(int i = 0; i < N; i++)
        p[i] = 0;
    for(int i = 1; i <= N - 5; i++)
        bit[i] = inf;
    for(int i = 1; i <= m; i++) {
        int x;
        scanf("%d", &x);
        for(int l = 0; l < N; l++) {
            if(x * l >= N) break;
            p[x * l] = max(p[x * l], x);
        }
    }
    for(int i = 0; i <= N - 5; i++) {
        dp[i] = get(i);
        if(!p[i]) continue;
        update(i + p[i] - 1, dp[i] + 1);
    }
    for(int i = 1; i <= q; i++) {
        int x;
        scanf("%d", &x);
        if(dp[x] == inf)
            printf("oo\n");
        else
            printf("%d\n", dp[x]);
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &q);
     ~~~~~^~~~~~~~~~~~~~~~
brunhilda.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
brunhilda.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 499 ms 117852 KB Output isn't correct
2 Incorrect 733 ms 117744 KB Output isn't correct
3 Incorrect 678 ms 117900 KB Output isn't correct
4 Incorrect 453 ms 117880 KB Output isn't correct
5 Incorrect 599 ms 117880 KB Output isn't correct
6 Incorrect 506 ms 117880 KB Output isn't correct
7 Incorrect 671 ms 117852 KB Output isn't correct
8 Incorrect 747 ms 117712 KB Output isn't correct
9 Incorrect 787 ms 117852 KB Output isn't correct
10 Incorrect 815 ms 117736 KB Output isn't correct
11 Incorrect 766 ms 117852 KB Output isn't correct
12 Incorrect 448 ms 117732 KB Output isn't correct
13 Incorrect 965 ms 117780 KB Output isn't correct
14 Execution timed out 1002 ms 117836 KB Time limit exceeded
15 Incorrect 752 ms 117752 KB Output isn't correct
16 Incorrect 748 ms 117820 KB Output isn't correct
17 Incorrect 578 ms 117780 KB Output isn't correct
18 Incorrect 463 ms 117916 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 583 ms 121188 KB Output isn't correct
2 Incorrect 685 ms 149208 KB Output isn't correct
3 Execution timed out 1066 ms 110396 KB Time limit exceeded
4 Incorrect 683 ms 118264 KB Output isn't correct
5 Execution timed out 1055 ms 122632 KB Time limit exceeded
6 Incorrect 688 ms 118236 KB Output isn't correct
7 Incorrect 639 ms 121080 KB Output isn't correct
8 Incorrect 642 ms 117876 KB Output isn't correct
9 Execution timed out 1079 ms 122768 KB Time limit exceeded
10 Execution timed out 1083 ms 112468 KB Time limit exceeded
11 Execution timed out 1077 ms 113656 KB Time limit exceeded
12 Incorrect 872 ms 118160 KB Output isn't correct
13 Incorrect 569 ms 119644 KB Output isn't correct
14 Incorrect 681 ms 118252 KB Output isn't correct
15 Execution timed out 1054 ms 120780 KB Time limit exceeded
16 Incorrect 673 ms 149168 KB Output isn't correct
17 Incorrect 978 ms 118028 KB Output isn't correct
18 Execution timed out 1067 ms 118972 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 114228 KB Time limit exceeded
2 Execution timed out 1081 ms 116528 KB Time limit exceeded
3 Execution timed out 1074 ms 115212 KB Time limit exceeded
4 Incorrect 882 ms 118520 KB Output isn't correct
5 Incorrect 793 ms 131116 KB Output isn't correct
6 Execution timed out 1020 ms 118572 KB Time limit exceeded
7 Execution timed out 1083 ms 124284 KB Time limit exceeded
8 Execution timed out 1070 ms 121572 KB Time limit exceeded
9 Execution timed out 1073 ms 121720 KB Time limit exceeded
10 Incorrect 864 ms 118284 KB Output isn't correct
11 Incorrect 799 ms 118168 KB Output isn't correct
12 Incorrect 973 ms 118212 KB Output isn't correct
13 Execution timed out 1074 ms 114512 KB Time limit exceeded
14 Incorrect 889 ms 117976 KB Output isn't correct
15 Execution timed out 1081 ms 117992 KB Time limit exceeded
16 Execution timed out 1056 ms 116688 KB Time limit exceeded
17 Execution timed out 1082 ms 118276 KB Time limit exceeded
18 Execution timed out 1089 ms 110200 KB Time limit exceeded
19 Incorrect 656 ms 120440 KB Output isn't correct
20 Execution timed out 1076 ms 115272 KB Time limit exceeded
21 Incorrect 933 ms 117964 KB Output isn't correct
22 Execution timed out 1091 ms 114488 KB Time limit exceeded
23 Incorrect 706 ms 121928 KB Output isn't correct
24 Incorrect 592 ms 118244 KB Output isn't correct
25 Incorrect 909 ms 118388 KB Output isn't correct
26 Incorrect 881 ms 118344 KB Output isn't correct
27 Execution timed out 1081 ms 111800 KB Time limit exceeded
28 Incorrect 641 ms 118392 KB Output isn't correct
29 Execution timed out 1095 ms 117368 KB Time limit exceeded
30 Execution timed out 1065 ms 112356 KB Time limit exceeded
31 Incorrect 730 ms 119044 KB Output isn't correct
32 Incorrect 750 ms 118284 KB Output isn't correct
33 Incorrect 509 ms 118648 KB Output isn't correct
34 Execution timed out 1027 ms 125648 KB Time limit exceeded
35 Incorrect 662 ms 118356 KB Output isn't correct
36 Execution timed out 1078 ms 115264 KB Time limit exceeded
37 Incorrect 757 ms 131128 KB Output isn't correct
38 Execution timed out 1018 ms 118440 KB Time limit exceeded
39 Incorrect 608 ms 118488 KB Output isn't correct
40 Incorrect 984 ms 118724 KB Output isn't correct
41 Execution timed out 1047 ms 130480 KB Time limit exceeded
42 Execution timed out 1029 ms 118152 KB Time limit exceeded