oj.uz

Submission #155738

# Submission time Handle Problem Language Result Execution time Memory
155738 2019-09-30T07:30:32 Z souhhcong Brunhilda’s Birthday (BOI13_brunhilda) C++14
2.22222 / 100
 86 ms 40212 KB 
#include <iostream>
#include <string.h>
using namespace std;

const int N = 1e5+5, MAXN = 1e7+7, INF = 1e9+9;
int n, q, x, p[N], dp[MAXN];

int solve(int x)
{
    //cout << x << endl;
    if (dp[x] != -1)
        return dp[x];
    int mn = INF;
    for (int i = n-1; i >= 0; i--)
    {
        if (!(x%p[i])) continue;
        mn = min(mn,solve(x/p[i]*p[i])+1);
    }
    dp[x] = mn;
    return dp[x];
}

int main()
{
    memset(dp,-1,sizeof dp);
    scanf("%d %d",&n,&q);
    for (int i = 0; i < n; i++)
    {
        scanf("%d",&p[i]);
    }
    for (int i = 1; i < p[n-1]; i++)
        dp[i] = 1;
    while(q--)
    {
        scanf("%d",&x);
        if (x < p[n-1]) printf("%d\n",dp[x]);

        int tmp = 1;
        for (int i = 0; i < n-1; i++)
        {
            tmp *= p[i];
            if (tmp > x) break;
        }
        if (tmp > x)
        {
            if (x % p[n-1] == 0)
            {
                printf("%d\n",2*x/p[n-1]);
            }
            else
            {
                printf("%d\n",2*x/p[n-1]+1);
            }
        }
        else
        {
            bool check = 1;
            for (int i = 0; i < n-1; i++)
            {
                if (x % p[i] != 0) check = 0;
            }
            if (check) printf("oo\n");
            else
            {
                if (x % p[n-1] == 0)
                {
                    printf("%d\n",2*(x/p[n-1]));
                }
                else
                {
                    printf("%d\n",2*(x/p[n-1])+1);
                }
            }
        }
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
brunhilda.cpp:35: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 36 ms 39544 KB Output isn't correct
2 Incorrect 35 ms 39544 KB Output isn't correct
3 Incorrect 36 ms 39416 KB Output isn't correct
4 Incorrect 37 ms 39460 KB Output isn't correct
5 Incorrect 35 ms 39544 KB Output isn't correct
6 Incorrect 35 ms 39492 KB Output isn't correct
7 Incorrect 35 ms 39544 KB Output isn't correct
8 Incorrect 35 ms 39476 KB Output isn't correct
9 Incorrect 34 ms 39416 KB Output isn't correct
10 Incorrect 35 ms 39388 KB Output isn't correct
11 Incorrect 35 ms 39388 KB Output isn't correct
12 Incorrect 35 ms 39416 KB Output isn't correct
13 Incorrect 36 ms 39544 KB Output isn't correct
14 Incorrect 38 ms 39416 KB Output isn't correct
15 Incorrect 41 ms 39416 KB Output isn't correct
16 Incorrect 35 ms 39416 KB Output isn't correct
17 Incorrect 43 ms 39288 KB Output isn't correct
18 Incorrect 43 ms 39544 KB Output isn't correct

Subtask #2
2.22222222222 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 39544 KB Output isn't correct
2 Correct 53 ms 39800 KB Output is correct
3 Incorrect 45 ms 39756 KB Output isn't correct
4 Incorrect 42 ms 39416 KB Output isn't correct
5 Incorrect 57 ms 39648 KB Output isn't correct
6 Incorrect 35 ms 39416 KB Output isn't correct
7 Incorrect 37 ms 39544 KB Output isn't correct
8 Incorrect 35 ms 39416 KB Output isn't correct
9 Incorrect 51 ms 39800 KB Output isn't correct
10 Incorrect 46 ms 39772 KB Output isn't correct
11 Incorrect 49 ms 39676 KB Output isn't correct
12 Incorrect 42 ms 39416 KB Output isn't correct
13 Incorrect 36 ms 39544 KB Output isn't correct
14 Incorrect 35 ms 39416 KB Output isn't correct
15 Incorrect 41 ms 39672 KB Output isn't correct
16 Correct 54 ms 39928 KB Output is correct
17 Incorrect 40 ms 39416 KB Output isn't correct
18 Incorrect 59 ms 39812 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 39796 KB Output isn't correct
2 Incorrect 53 ms 39684 KB Output isn't correct
3 Incorrect 63 ms 39800 KB Output isn't correct
4 Incorrect 68 ms 39800 KB Output isn't correct
5 Incorrect 86 ms 40056 KB Output isn't correct
6 Incorrect 70 ms 39800 KB Output isn't correct
7 Incorrect 70 ms 39928 KB Output isn't correct
8 Incorrect 61 ms 39800 KB Output isn't correct
9 Incorrect 57 ms 39800 KB Output isn't correct
10 Incorrect 40 ms 39544 KB Output isn't correct
11 Incorrect 42 ms 39544 KB Output isn't correct
12 Incorrect 42 ms 39544 KB Output isn't correct
13 Incorrect 70 ms 39800 KB Output isn't correct
14 Incorrect 61 ms 40056 KB Output isn't correct
15 Incorrect 46 ms 39700 KB Output isn't correct
16 Incorrect 42 ms 39544 KB Output isn't correct
17 Incorrect 45 ms 39708 KB Output isn't correct
18 Incorrect 54 ms 39800 KB Output isn't correct
19 Incorrect 49 ms 39544 KB Output isn't correct
20 Incorrect 63 ms 39804 KB Output isn't correct
21 Incorrect 69 ms 40056 KB Output isn't correct
22 Incorrect 77 ms 40184 KB Output isn't correct
23 Incorrect 68 ms 39928 KB Output isn't correct
24 Incorrect 69 ms 39928 KB Output isn't correct
25 Incorrect 63 ms 39800 KB Output isn't correct
26 Incorrect 63 ms 39800 KB Output isn't correct
27 Incorrect 63 ms 40056 KB Output isn't correct
28 Incorrect 78 ms 39800 KB Output isn't correct
29 Incorrect 84 ms 40212 KB Output isn't correct
30 Incorrect 73 ms 40056 KB Output isn't correct
31 Incorrect 62 ms 39704 KB Output isn't correct
32 Incorrect 62 ms 39800 KB Output isn't correct
33 Incorrect 68 ms 39728 KB Output isn't correct
34 Incorrect 64 ms 39928 KB Output isn't correct
35 Incorrect 69 ms 39928 KB Output isn't correct
36 Incorrect 81 ms 40136 KB Output isn't correct
37 Incorrect 79 ms 40056 KB Output isn't correct
38 Incorrect 67 ms 39840 KB Output isn't correct
39 Incorrect 76 ms 39800 KB Output isn't correct
40 Incorrect 63 ms 39772 KB Output isn't correct
41 Incorrect 77 ms 40140 KB Output isn't correct
42 Incorrect 65 ms 39972 KB Output isn't correct