답안 #493718

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493718	2021-12-12T17:41:51 Z	_Monkey_	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	77.4603 / 100	237 ms	262148 KB

brunhilda

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
#define el '\n'
#define ld long double
const int maxn=1e5+1,nn=1e7+1;
void amax(int &x,int y){if(y>x)x=y;}
int a[maxn],n,m,q,p,oo,ans,k,f[nn],ut[nn];
int t;
bool ok;
void check(){
    t=1;
    ok=0;
    for(int i=0;i<m;++i){
        k=t*a[i];
        if(t*a[i]<t || t*a[i]>oo || k/a[i]!=t){
            ok=1;
            return;
        }
        t=t*a[i];
    }
}
int sol(int z){
    if(f[z]>=0) return f[z];
    f[z]=sol(z-ut[z])+1;
    return f[z];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> m >> q;
    for(int i=0;i<m;++i) cin >> a[i];
    sort(a+0,a+m);
  	for(int i=0;i<m;++i)
        for(int j=a[i]-1;j<nn;j+=a[i]) ut[j]=a[i]-1;
    for(int i=nn-2;i>0;--i) amax(ut[i],ut[i+1]-1);
    memset(f,-1,sizeof f);
    f[0]=0;
    oo=1e7;
    check();
    while(q--){
        cin >> n;
        if(ok){
            cout << sol(n);
        } else {
            if(n>=t){
                cout << "oo";
            } else {
                cout << sol(n);
            }
        }
        cout << el;
    }
    return 0;
}

Subtask #1

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	71 ms	78484 KB	Output is correct
2	Correct	86 ms	78480 KB	Output is correct
3	Correct	71 ms	78484 KB	Output is correct
4	Correct	68 ms	78476 KB	Output is correct
5	Correct	72 ms	78532 KB	Output is correct
6	Correct	66 ms	78476 KB	Output is correct
7	Correct	68 ms	78484 KB	Output is correct
8	Correct	82 ms	78536 KB	Output is correct
9	Correct	96 ms	78480 KB	Output is correct
10	Correct	102 ms	78480 KB	Output is correct
11	Correct	98 ms	78496 KB	Output is correct
12	Correct	67 ms	78476 KB	Output is correct
13	Correct	174 ms	78484 KB	Output is correct
14	Correct	182 ms	78484 KB	Output is correct
15	Correct	81 ms	78532 KB	Output is correct
16	Correct	77 ms	78540 KB	Output is correct
17	Correct	82 ms	78492 KB	Output is correct
18	Correct	75 ms	78616 KB	Output is correct

Subtask #2

18.8888888889 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	70 ms	78576 KB	Output is correct
2	Correct	80 ms	78836 KB	Output is correct
3	Correct	217 ms	78748 KB	Output is correct
4	Correct	85 ms	78504 KB	Output is correct
5	Correct	137 ms	78676 KB	Output is correct
6	Correct	77 ms	78544 KB	Output is correct
7	Correct	82 ms	78536 KB	Output is correct
8	Correct	98 ms	78552 KB	Output is correct
9	Correct	153 ms	78764 KB	Output is correct
10	Correct	207 ms	78788 KB	Output is correct
11	Incorrect	186 ms	78660 KB	Output isn't correct
12	Correct	118 ms	78492 KB	Output is correct
13	Correct	71 ms	78500 KB	Output is correct
14	Correct	87 ms	78576 KB	Output is correct
15	Correct	155 ms	78772 KB	Output is correct
16	Correct	111 ms	78832 KB	Output is correct
17	Correct	163 ms	78488 KB	Output is correct
18	Correct	158 ms	78864 KB	Output is correct

Subtask #3

38.5714285714 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Correct	191 ms	78852 KB	Output is correct
2	Correct	211 ms	78812 KB	Output is correct
3	Correct	208 ms	78932 KB	Output is correct
4	Incorrect	154 ms	78744 KB	Output isn't correct
5	Runtime error	202 ms	262148 KB	Execution killed with signal 9
6	Correct	186 ms	78764 KB	Output is correct
7	Correct	147 ms	78976 KB	Output is correct
8	Correct	173 ms	78820 KB	Output is correct
9	Correct	173 ms	78788 KB	Output is correct
10	Correct	128 ms	78632 KB	Output is correct
11	Incorrect	139 ms	78624 KB	Output isn't correct
12	Correct	159 ms	78628 KB	Output is correct
13	Correct	184 ms	78928 KB	Output is correct
14	Correct	132 ms	79888 KB	Output is correct
15	Incorrect	164 ms	78732 KB	Output isn't correct
16	Correct	182 ms	78648 KB	Output is correct
17	Correct	158 ms	78784 KB	Output is correct
18	Correct	233 ms	78816 KB	Output is correct
19	Incorrect	76 ms	78624 KB	Output isn't correct
20	Correct	191 ms	79052 KB	Output is correct
21	Incorrect	139 ms	79300 KB	Output isn't correct
22	Correct	221 ms	79056 KB	Output is correct
23	Correct	118 ms	78884 KB	Output is correct
24	Correct	97 ms	78892 KB	Output is correct
25	Incorrect	155 ms	78876 KB	Output isn't correct
26	Incorrect	138 ms	78788 KB	Output isn't correct
27	Correct	215 ms	79116 KB	Output is correct
28	Runtime error	200 ms	262148 KB	Execution killed with signal 9
29	Correct	208 ms	79052 KB	Output is correct
30	Correct	204 ms	79008 KB	Output is correct
31	Correct	107 ms	78764 KB	Output is correct
32	Incorrect	119 ms	78788 KB	Output isn't correct
33	Incorrect	91 ms	78752 KB	Output isn't correct
34	Correct	153 ms	79020 KB	Output is correct
35	Runtime error	197 ms	262148 KB	Execution killed with signal 9
36	Correct	237 ms	79092 KB	Output is correct
37	Runtime error	208 ms	262148 KB	Execution killed with signal 9
38	Correct	190 ms	78772 KB	Output is correct
39	Incorrect	105 ms	78788 KB	Output isn't correct
40	Correct	161 ms	78776 KB	Output is correct
41	Correct	135 ms	78976 KB	Output is correct
42	Incorrect	187 ms	78888 KB	Output isn't correct