Submission #156533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
156533	2019-10-06T10:58:16 Z	combi1k1	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	74.127 / 100	431 ms	80428 KB

brunhilda

#include<bits/stdc++.h>

using namespace std;

const int   N   = 1e7 + 1;

int f[N];
int g[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int m;  cin >> m;
    int q;  cin >> q;

    for(int i = 1 ; i < N ; ++i)    f[i] = i;
    for(int i = 0 ; i < m ; ++i)    {
        int x;  cin >> x;
        for(int j = x ; j < N ; j += x)
            f[j - 1] = min(f[j - 1],j - x);
    }

    for(int i = N - 2 ; i ; --i)
        f[i] = min(f[i],f[i + 1]);

    for(int i = 1 ; i < N ; ++i)    {
        if (f[i] == i)
            g[i] = 1e9;
        else
            g[i] = g[f[i]] + 1;
    }

    //for(int i = 1 ; i < 10 ; ++i)
    //    cout << f[i] << " ";

    //cout << "\n";

    for(int i = 0 ; i < q ; ++i)    {
        int x;  cin >> x;
        if (g[x] == 1e9)
            cout << "oo\n";
        else
            cout << g[x] << "\n";
    }
}

Subtask #1

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	124 ms	78712 KB	Output isn't correct
2	Correct	141 ms	78584 KB	Output is correct
3	Correct	132 ms	78592 KB	Output is correct
4	Correct	121 ms	78840 KB	Output is correct
5	Correct	136 ms	78584 KB	Output is correct
6	Incorrect	126 ms	78712 KB	Output isn't correct
7	Correct	132 ms	78584 KB	Output is correct
8	Correct	137 ms	78568 KB	Output is correct
9	Correct	153 ms	78584 KB	Output is correct
10	Correct	173 ms	78584 KB	Output is correct
11	Correct	166 ms	78584 KB	Output is correct
12	Correct	116 ms	78584 KB	Output is correct
13	Correct	266 ms	78584 KB	Output is correct
14	Correct	270 ms	78712 KB	Output is correct
15	Correct	154 ms	78568 KB	Output is correct
16	Correct	141 ms	78676 KB	Output is correct
17	Correct	140 ms	78740 KB	Output is correct
18	Correct	121 ms	78684 KB	Output is correct

Subtask #2

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	78712 KB	Output is correct
2	Correct	158 ms	79388 KB	Output is correct
3	Correct	325 ms	79096 KB	Output is correct
4	Correct	161 ms	78712 KB	Output is correct
5	Correct	236 ms	78992 KB	Output is correct
6	Correct	156 ms	78592 KB	Output is correct
7	Correct	137 ms	78708 KB	Output is correct
8	Correct	158 ms	78584 KB	Output is correct
9	Correct	274 ms	79092 KB	Output is correct
10	Correct	329 ms	79088 KB	Output is correct
11	Incorrect	320 ms	78968 KB	Output isn't correct
12	Correct	193 ms	78584 KB	Output is correct
13	Correct	130 ms	78576 KB	Output is correct
14	Correct	162 ms	78584 KB	Output is correct
15	Correct	277 ms	78840 KB	Output is correct
16	Correct	157 ms	79352 KB	Output is correct
17	Correct	272 ms	78840 KB	Output is correct
18	Incorrect	380 ms	79348 KB	Output isn't correct

Subtask #3

38.5714285714 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	279 ms	79352 KB	Output is correct
2	Correct	329 ms	79128 KB	Output is correct
3	Correct	331 ms	79532 KB	Output is correct
4	Incorrect	219 ms	79600 KB	Output isn't correct
5	Incorrect	187 ms	80344 KB	Output isn't correct
6	Correct	286 ms	79612 KB	Output is correct
7	Correct	277 ms	79832 KB	Output is correct
8	Correct	292 ms	79532 KB	Output is correct
9	Correct	282 ms	79356 KB	Output is correct
10	Correct	231 ms	78864 KB	Output is correct
11	Incorrect	225 ms	78968 KB	Output isn't correct
12	Correct	258 ms	78800 KB	Output is correct
13	Correct	344 ms	79856 KB	Output is correct
14	Correct	231 ms	79864 KB	Output is correct
15	Incorrect	268 ms	78960 KB	Output isn't correct
16	Correct	288 ms	78840 KB	Output is correct
17	Correct	265 ms	78968 KB	Output is correct
18	Correct	431 ms	79224 KB	Output is correct
19	Incorrect	138 ms	78840 KB	Output isn't correct
20	Correct	385 ms	79732 KB	Output is correct
21	Incorrect	227 ms	79988 KB	Output isn't correct
22	Correct	342 ms	80380 KB	Output is correct
23	Correct	181 ms	79860 KB	Output is correct
24	Correct	158 ms	79608 KB	Output is correct
25	Incorrect	239 ms	79608 KB	Output isn't correct
26	Incorrect	224 ms	79676 KB	Output isn't correct
27	Correct	422 ms	79864 KB	Output is correct
28	Incorrect	161 ms	79764 KB	Output isn't correct
29	Correct	330 ms	80428 KB	Output is correct
30	Correct	293 ms	80120 KB	Output is correct
31	Correct	180 ms	79608 KB	Output is correct
32	Incorrect	190 ms	79644 KB	Output isn't correct
33	Incorrect	146 ms	79608 KB	Output isn't correct
34	Correct	259 ms	79920 KB	Output is correct
35	Incorrect	187 ms	79740 KB	Output isn't correct
36	Correct	364 ms	80376 KB	Output is correct
37	Incorrect	209 ms	80376 KB	Output isn't correct
38	Correct	321 ms	79740 KB	Output is correct
39	Incorrect	171 ms	79608 KB	Output isn't correct
40	Correct	260 ms	79604 KB	Output is correct
41	Correct	280 ms	79864 KB	Output is correct
42	Incorrect	313 ms	79860 KB	Output isn't correct