oj.uz

답안 #493711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
493711 2021-12-12T16:34:17 Z _Monkey_ Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 51 ms 78772 KB 
#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(){
    freopen("T.INP","r",stdin);
    freopen("T.OUT","w",stdout);
    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;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:28:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     freopen("T.INP","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:29:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |     freopen("T.OUT","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 78524 KB Output isn't correct
2 Incorrect 41 ms 78516 KB Output isn't correct
3 Incorrect 43 ms 78552 KB Output isn't correct
4 Incorrect 44 ms 78540 KB Output isn't correct
5 Incorrect 43 ms 78600 KB Output isn't correct
6 Incorrect 46 ms 78532 KB Output isn't correct
7 Incorrect 42 ms 78640 KB Output isn't correct
8 Incorrect 44 ms 78556 KB Output isn't correct
9 Incorrect 45 ms 78560 KB Output isn't correct
10 Incorrect 45 ms 78772 KB Output isn't correct
11 Incorrect 43 ms 78544 KB Output isn't correct
12 Incorrect 43 ms 78532 KB Output isn't correct
13 Incorrect 45 ms 78576 KB Output isn't correct
14 Incorrect 43 ms 78520 KB Output isn't correct
15 Incorrect 42 ms 78532 KB Output isn't correct
16 Incorrect 43 ms 78528 KB Output isn't correct
17 Incorrect 41 ms 78632 KB Output isn't correct
18 Incorrect 43 ms 78548 KB Output isn't correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 78532 KB Output isn't correct
2 Incorrect 44 ms 78564 KB Output isn't correct
3 Incorrect 47 ms 78576 KB Output isn't correct
4 Incorrect 46 ms 78524 KB Output isn't correct
5 Incorrect 43 ms 78576 KB Output isn't correct
6 Incorrect 44 ms 78584 KB Output isn't correct
7 Incorrect 43 ms 78576 KB Output isn't correct
8 Incorrect 43 ms 78544 KB Output isn't correct
9 Incorrect 43 ms 78588 KB Output isn't correct
10 Incorrect 43 ms 78584 KB Output isn't correct
11 Incorrect 43 ms 78524 KB Output isn't correct
12 Incorrect 43 ms 78544 KB Output isn't correct
13 Incorrect 42 ms 78512 KB Output isn't correct
14 Incorrect 43 ms 78532 KB Output isn't correct
15 Incorrect 43 ms 78532 KB Output isn't correct
16 Incorrect 43 ms 78532 KB Output isn't correct
17 Incorrect 51 ms 78536 KB Output isn't correct
18 Incorrect 46 ms 78616 KB Output isn't correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 78592 KB Output isn't correct
2 Incorrect 44 ms 78596 KB Output isn't correct
3 Incorrect 44 ms 78520 KB Output isn't correct
4 Incorrect 45 ms 78640 KB Output isn't correct
5 Incorrect 41 ms 78628 KB Output isn't correct
6 Incorrect 44 ms 78612 KB Output isn't correct
7 Incorrect 42 ms 78604 KB Output isn't correct
8 Incorrect 43 ms 78600 KB Output isn't correct
9 Incorrect 42 ms 78516 KB Output isn't correct
10 Incorrect 42 ms 78532 KB Output isn't correct
11 Incorrect 42 ms 78532 KB Output isn't correct
12 Incorrect 42 ms 78636 KB Output isn't correct
13 Incorrect 46 ms 78556 KB Output isn't correct
14 Incorrect 44 ms 78644 KB Output isn't correct
15 Incorrect 45 ms 78588 KB Output isn't correct
16 Incorrect 49 ms 78532 KB Output isn't correct
17 Incorrect 43 ms 78564 KB Output isn't correct
18 Incorrect 44 ms 78540 KB Output isn't correct
19 Incorrect 43 ms 78568 KB Output isn't correct
20 Incorrect 43 ms 78564 KB Output isn't correct
21 Incorrect 42 ms 78528 KB Output isn't correct
22 Incorrect 43 ms 78624 KB Output isn't correct
23 Incorrect 43 ms 78616 KB Output isn't correct
24 Incorrect 42 ms 78632 KB Output isn't correct
25 Incorrect 43 ms 78536 KB Output isn't correct
26 Incorrect 44 ms 78516 KB Output isn't correct
27 Incorrect 44 ms 78528 KB Output isn't correct
28 Incorrect 43 ms 78636 KB Output isn't correct
29 Incorrect 45 ms 78592 KB Output isn't correct
30 Incorrect 42 ms 78524 KB Output isn't correct
31 Incorrect 45 ms 78628 KB Output isn't correct
32 Incorrect 44 ms 78560 KB Output isn't correct
33 Incorrect 42 ms 78600 KB Output isn't correct
34 Incorrect 42 ms 78548 KB Output isn't correct
35 Incorrect 42 ms 78580 KB Output isn't correct
36 Incorrect 44 ms 78728 KB Output isn't correct
37 Incorrect 42 ms 78620 KB Output isn't correct
38 Incorrect 44 ms 78664 KB Output isn't correct
39 Incorrect 50 ms 78620 KB Output isn't correct
40 Incorrect 42 ms 78536 KB Output isn't correct
41 Incorrect 44 ms 78596 KB Output isn't correct
42 Incorrect 42 ms 78532 KB Output isn't correct