답안 #493712

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
493712	2021-12-12T16:34:48 Z	_Monkey_	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	1.11111 / 100	1000 ms	81208 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;
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];
    return f[z]=sol(z-ut[z])+1;
}
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);
    memset(f,-1,sizeof f);
    f[0]=0;
    for(int i=0;i<m;++i){
        for(int j=1;j*a[i]<nn;j++){
            ut[j*a[i]-1]=max(a[i]-1,ut[j*a[i]-1]);
        }
    }
    int ma;
    for(int i=1;i<a[m-1];++i) ut[i]=i;
    for(int z=a[m-1];z<nn;++z)
        if(ut[z]==0){
            ma=0;
            for(int i=m-1;i>=0;--i){
                if(ma>=a[i]) break;
                if(z%a[i]>ma) ma=z%a[i];
            }
            ut[z]=ma;
        }
    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

1.11111111111 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	203 ms	78576 KB	Output isn't correct
2	Incorrect	238 ms	78492 KB	Output isn't correct
3	Incorrect	124 ms	78532 KB	Output isn't correct
4	Incorrect	527 ms	78572 KB	Output isn't correct
5	Incorrect	297 ms	78472 KB	Output isn't correct
6	Incorrect	203 ms	78576 KB	Output isn't correct
7	Incorrect	109 ms	78520 KB	Output isn't correct
8	Incorrect	98 ms	78568 KB	Output isn't correct
9	Incorrect	115 ms	78504 KB	Output isn't correct
10	Incorrect	130 ms	78588 KB	Output isn't correct
11	Incorrect	172 ms	78604 KB	Output isn't correct
12	Execution timed out	1089 ms	78532 KB	Time limit exceeded
13	Incorrect	326 ms	78492 KB	Output isn't correct
14	Correct	347 ms	78660 KB	Output is correct
15	Incorrect	206 ms	78568 KB	Output isn't correct
16	Incorrect	233 ms	78580 KB	Output isn't correct
17	Incorrect	387 ms	78576 KB	Output isn't correct
18	Incorrect	526 ms	78572 KB	Output isn't correct

Subtask #2

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1081 ms	78528 KB	Time limit exceeded
2	Execution timed out	1095 ms	78932 KB	Time limit exceeded
3	Execution timed out	1093 ms	78780 KB	Time limit exceeded
4	Execution timed out	1097 ms	78532 KB	Time limit exceeded
5	Execution timed out	1097 ms	78828 KB	Time limit exceeded
6	Execution timed out	1086 ms	78536 KB	Time limit exceeded
7	Execution timed out	1095 ms	78532 KB	Time limit exceeded
8	Execution timed out	1095 ms	78532 KB	Time limit exceeded
9	Execution timed out	1093 ms	78796 KB	Time limit exceeded
10	Execution timed out	1085 ms	78724 KB	Time limit exceeded
11	Execution timed out	1041 ms	78664 KB	Time limit exceeded
12	Incorrect	957 ms	78588 KB	Output isn't correct
13	Execution timed out	1096 ms	78540 KB	Time limit exceeded
14	Execution timed out	1093 ms	78556 KB	Time limit exceeded
15	Execution timed out	1093 ms	78668 KB	Time limit exceeded
16	Execution timed out	1088 ms	78860 KB	Time limit exceeded
17	Incorrect	316 ms	78592 KB	Output isn't correct
18	Execution timed out	1074 ms	78916 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1093 ms	78712 KB	Time limit exceeded
2	Execution timed out	1093 ms	78796 KB	Time limit exceeded
3	Execution timed out	1094 ms	78724 KB	Time limit exceeded
4	Execution timed out	1091 ms	78532 KB	Time limit exceeded
5	Execution timed out	1097 ms	78912 KB	Time limit exceeded
6	Execution timed out	1094 ms	78532 KB	Time limit exceeded
7	Execution timed out	1086 ms	78880 KB	Time limit exceeded
8	Execution timed out	1087 ms	78660 KB	Time limit exceeded
9	Execution timed out	1093 ms	78748 KB	Time limit exceeded
10	Execution timed out	1090 ms	78540 KB	Time limit exceeded
11	Execution timed out	1097 ms	78476 KB	Time limit exceeded
12	Execution timed out	1088 ms	78540 KB	Time limit exceeded
13	Execution timed out	1089 ms	78592 KB	Time limit exceeded
14	Incorrect	190 ms	81208 KB	Output isn't correct
15	Incorrect	793 ms	78604 KB	Output isn't correct
16	Incorrect	850 ms	78660 KB	Output isn't correct
17	Execution timed out	1087 ms	78684 KB	Time limit exceeded
18	Execution timed out	1092 ms	78788 KB	Time limit exceeded
19	Execution timed out	1101 ms	78556 KB	Time limit exceeded
20	Execution timed out	1078 ms	78748 KB	Time limit exceeded
21	Incorrect	185 ms	79812 KB	Output isn't correct
22	Execution timed out	1101 ms	78908 KB	Time limit exceeded
23	Execution timed out	1100 ms	78660 KB	Time limit exceeded
24	Execution timed out	1091 ms	78532 KB	Time limit exceeded
25	Execution timed out	1094 ms	78520 KB	Time limit exceeded
26	Execution timed out	1097 ms	78536 KB	Time limit exceeded
27	Execution timed out	1098 ms	78868 KB	Time limit exceeded
28	Incorrect	965 ms	78968 KB	Output isn't correct
29	Execution timed out	1084 ms	78908 KB	Time limit exceeded
30	Execution timed out	1085 ms	78820 KB	Time limit exceeded
31	Execution timed out	1098 ms	78532 KB	Time limit exceeded
32	Execution timed out	1095 ms	78540 KB	Time limit exceeded
33	Execution timed out	1083 ms	78532 KB	Time limit exceeded
34	Execution timed out	1098 ms	78916 KB	Time limit exceeded
35	Execution timed out	1092 ms	78492 KB	Time limit exceeded
36	Execution timed out	1098 ms	78880 KB	Time limit exceeded
37	Execution timed out	1099 ms	78916 KB	Time limit exceeded
38	Execution timed out	1094 ms	78532 KB	Time limit exceeded
39	Execution timed out	1094 ms	78504 KB	Time limit exceeded
40	Execution timed out	1097 ms	78544 KB	Time limit exceeded
41	Execution timed out	1100 ms	78916 KB	Time limit exceeded
42	Incorrect	357 ms	79136 KB	Output isn't correct