oj.uz

Submission #155739

# Submission time Handle Problem Language Result Execution time Memory
155739 2019-09-30T07:32:52 Z souhhcong Brunhilda’s Birthday (BOI13_brunhilda) C++14
5.55556 / 100
 82 ms 40180 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 (n == 1)
        {
            if (x >= p[0]) printf("oo\n");
            else printf("1\n");
            continue;
        }
        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 35 ms 39416 KB Output isn't correct
2 Incorrect 36 ms 39416 KB Output isn't correct
3 Incorrect 34 ms 39428 KB Output isn't correct
4 Incorrect 37 ms 39544 KB Output isn't correct
5 Incorrect 35 ms 39440 KB Output isn't correct
6 Incorrect 36 ms 39416 KB Output isn't correct
7 Incorrect 35 ms 39544 KB Output isn't correct
8 Incorrect 35 ms 39416 KB Output isn't correct
9 Incorrect 35 ms 39416 KB Output isn't correct
10 Incorrect 35 ms 39388 KB Output isn't correct
11 Incorrect 42 ms 39416 KB Output isn't correct
12 Incorrect 40 ms 39416 KB Output isn't correct
13 Incorrect 42 ms 39416 KB Output isn't correct
14 Incorrect 38 ms 39464 KB Output isn't correct
15 Incorrect 35 ms 39416 KB Output isn't correct
16 Incorrect 35 ms 39416 KB Output isn't correct
17 Incorrect 37 ms 39672 KB Output isn't correct
18 Incorrect 38 ms 39532 KB Output isn't correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 39548 KB Output isn't correct
2 Correct 54 ms 39972 KB Output is correct
3 Correct 46 ms 39776 KB Output is correct
4 Incorrect 35 ms 39456 KB Output isn't correct
5 Correct 43 ms 39672 KB Output is correct
6 Incorrect 35 ms 39416 KB Output isn't correct
7 Incorrect 37 ms 39516 KB Output isn't correct
8 Incorrect 41 ms 39416 KB Output isn't correct
9 Incorrect 51 ms 39672 KB Output isn't correct
10 Correct 52 ms 39752 KB Output is correct
11 Incorrect 47 ms 39672 KB Output isn't correct
12 Incorrect 36 ms 39516 KB Output isn't correct
13 Incorrect 36 ms 39416 KB Output isn't correct
14 Incorrect 35 ms 39412 KB Output isn't correct
15 Incorrect 48 ms 39672 KB Output isn't correct
16 Correct 54 ms 39800 KB Output is correct
17 Incorrect 35 ms 39416 KB Output isn't correct
18 Incorrect 53 ms 39800 KB Output isn't correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 39800 KB Output isn't correct
2 Incorrect 49 ms 39772 KB Output isn't correct
3 Incorrect 59 ms 40024 KB Output isn't correct
4 Incorrect 63 ms 39772 KB Output isn't correct
5 Incorrect 82 ms 40004 KB Output isn't correct
6 Incorrect 64 ms 39800 KB Output isn't correct
7 Incorrect 65 ms 39928 KB Output isn't correct
8 Incorrect 53 ms 39800 KB Output isn't correct
9 Incorrect 54 ms 39800 KB Output isn't correct
10 Incorrect 39 ms 39464 KB Output isn't correct
11 Incorrect 42 ms 39588 KB Output isn't correct
12 Incorrect 42 ms 39544 KB Output isn't correct
13 Incorrect 63 ms 39800 KB Output isn't correct
14 Incorrect 66 ms 40040 KB Output isn't correct
15 Incorrect 43 ms 39516 KB Output isn't correct
16 Incorrect 45 ms 39556 KB Output isn't correct
17 Incorrect 46 ms 39764 KB Output isn't correct
18 Incorrect 50 ms 39820 KB Output isn't correct
19 Incorrect 42 ms 39544 KB Output isn't correct
20 Incorrect 57 ms 39800 KB Output isn't correct
21 Incorrect 62 ms 40056 KB Output isn't correct
22 Incorrect 78 ms 40180 KB Output isn't correct
23 Incorrect 67 ms 39932 KB Output isn't correct
24 Incorrect 65 ms 39764 KB Output isn't correct
25 Incorrect 63 ms 39800 KB Output isn't correct
26 Incorrect 62 ms 39752 KB Output isn't correct
27 Incorrect 68 ms 40028 KB Output isn't correct
28 Incorrect 64 ms 39928 KB Output isn't correct
29 Incorrect 78 ms 40180 KB Output isn't correct
30 Incorrect 73 ms 40056 KB Output isn't correct
31 Incorrect 61 ms 39800 KB Output isn't correct
32 Incorrect 62 ms 39772 KB Output isn't correct
33 Incorrect 61 ms 39736 KB Output isn't correct
34 Incorrect 64 ms 39928 KB Output isn't correct
35 Incorrect 62 ms 39928 KB Output isn't correct
36 Incorrect 79 ms 40056 KB Output isn't correct
37 Incorrect 79 ms 40116 KB Output isn't correct
38 Incorrect 64 ms 39800 KB Output isn't correct
39 Incorrect 64 ms 39720 KB Output isn't correct
40 Incorrect 63 ms 39800 KB Output isn't correct
41 Incorrect 75 ms 40056 KB Output isn't correct
42 Incorrect 62 ms 39928 KB Output isn't correct