Submission #283227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283227	2020-08-25T11:40:05 Z	Atill83	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	40.1587 / 100	761 ms	41976 KB

brunhilda

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 1e7+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll m, q;
ll p[(int)1e5 + 5];
int ans[MAXN];



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

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>m>>q;
    memset(ans, 0x7f, sizeof(ans));
    for(int i = 0; i < m; i++){
        cin>>p[i];
    }

    for(int i = 1; i < p[m - 1]; i++){
        ans[i] = 1;
    }

    for(int i = p[m - 1]; i <= 1e7; i++){
        //int mnI = -1;
        for(int j = m - 1; j >= max(m - 8, 0LL); j--){
            if(i % p[j] == 0) continue;
            if(ans[i - i % p[j]] + 1 < ans[i]){
                ans[i] = ans[i - i % p[j]] + 1;
                //mnI = j;
            }
        }
        //cout<<ans[i]<<" "<<mnI<<endl;
    }

    for(int i = 0; i < q; i++){
        int n;
        cin>>n;
        if(ans[n] > 1e7){
            cout<<"oo"<<endl;
        }else{
            cout<<ans[n]<<endl;
        }
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1

13.3333333333 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	39544 KB	Output is correct
2	Incorrect	642 ms	39544 KB	Output isn't correct
3	Correct	486 ms	39424 KB	Output is correct
4	Incorrect	592 ms	39552 KB	Output isn't correct
5	Correct	702 ms	39672 KB	Output is correct
6	Correct	305 ms	39544 KB	Output is correct
7	Correct	484 ms	39544 KB	Output is correct
8	Correct	569 ms	39552 KB	Output is correct
9	Correct	761 ms	39672 KB	Output is correct
10	Correct	675 ms	39552 KB	Output is correct
11	Correct	676 ms	39672 KB	Output is correct
12	Correct	595 ms	39424 KB	Output is correct
13	Correct	569 ms	39548 KB	Output is correct
14	Correct	563 ms	39672 KB	Output is correct
15	Incorrect	637 ms	39416 KB	Output isn't correct
16	Incorrect	640 ms	39544 KB	Output isn't correct
17	Incorrect	637 ms	39548 KB	Output isn't correct
18	Incorrect	597 ms	39672 KB	Output isn't correct

Subtask #2

11.1111111111 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	440 ms	39800 KB	Output is correct
2	Correct	81 ms	40824 KB	Output is correct
3	Correct	374 ms	40572 KB	Output is correct
4	Incorrect	512 ms	39552 KB	Output isn't correct
5	Correct	415 ms	40284 KB	Output is correct
6	Incorrect	517 ms	39424 KB	Output isn't correct
7	Correct	452 ms	39800 KB	Output is correct
8	Incorrect	543 ms	39552 KB	Output isn't correct
9	Correct	416 ms	40588 KB	Output is correct
10	Correct	371 ms	40448 KB	Output is correct
11	Incorrect	459 ms	40184 KB	Output isn't correct
12	Incorrect	525 ms	39544 KB	Output isn't correct
13	Incorrect	465 ms	39552 KB	Output isn't correct
14	Incorrect	512 ms	39672 KB	Output isn't correct
15	Correct	442 ms	40192 KB	Output is correct
16	Correct	80 ms	40952 KB	Output is correct
17	Correct	541 ms	39672 KB	Output is correct
18	Incorrect	261 ms	41084 KB	Output isn't correct

Subtask #3

15.7142857143 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	448 ms	40568 KB	Output isn't correct
2	Incorrect	460 ms	40432 KB	Output isn't correct
3	Correct	455 ms	40824 KB	Output is correct
4	Incorrect	551 ms	40568 KB	Output isn't correct
5	Correct	311 ms	41848 KB	Output is correct
6	Incorrect	543 ms	40696 KB	Output isn't correct
7	Correct	351 ms	41568 KB	Output is correct
8	Incorrect	451 ms	40548 KB	Output isn't correct
9	Incorrect	448 ms	40568 KB	Output isn't correct
10	Incorrect	523 ms	39684 KB	Output isn't correct
11	Incorrect	525 ms	39804 KB	Output isn't correct
12	Incorrect	531 ms	39800 KB	Output isn't correct
13	Incorrect	481 ms	40952 KB	Output isn't correct
14	Incorrect	687 ms	40952 KB	Output isn't correct
15	Incorrect	530 ms	39808 KB	Output isn't correct
16	Incorrect	532 ms	39828 KB	Output isn't correct
17	Incorrect	455 ms	40312 KB	Output isn't correct
18	Incorrect	461 ms	40568 KB	Output isn't correct
19	Incorrect	452 ms	39928 KB	Output isn't correct
20	Correct	460 ms	40824 KB	Output is correct
21	Incorrect	640 ms	40832 KB	Output isn't correct
22	Correct	443 ms	41848 KB	Output is correct
23	Incorrect	462 ms	41080 KB	Output isn't correct
24	Incorrect	546 ms	40696 KB	Output isn't correct
25	Incorrect	556 ms	40600 KB	Output isn't correct
26	Incorrect	541 ms	40440 KB	Output isn't correct
27	Correct	413 ms	41464 KB	Output is correct
28	Incorrect	525 ms	40824 KB	Output isn't correct
29	Correct	441 ms	41976 KB	Output is correct
30	Incorrect	469 ms	41592 KB	Output isn't correct
31	Incorrect	508 ms	40440 KB	Output isn't correct
32	Incorrect	550 ms	40568 KB	Output isn't correct
33	Incorrect	523 ms	40544 KB	Output isn't correct
34	Correct	353 ms	41592 KB	Output is correct
35	Incorrect	527 ms	40696 KB	Output isn't correct
36	Correct	438 ms	41744 KB	Output is correct
37	Correct	297 ms	41848 KB	Output is correct
38	Incorrect	540 ms	40624 KB	Output isn't correct
39	Incorrect	548 ms	40620 KB	Output isn't correct
40	Incorrect	530 ms	40696 KB	Output isn't correct
41	Correct	166 ms	41572 KB	Output is correct
42	Incorrect	567 ms	40700 KB	Output isn't correct