Submission #742836

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
742836	2023-05-17T03:49:11 Z	irmuun	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	97.7778 / 100	601 ms	159024 KB

brunhilda

#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()

const int MAX=2e7+5;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m,q;
    cin>>m>>q;
    int p[m+5];
    for(int i=1;i<=m;i++){
        cin>>p[i];
    }
    vector<int>mn(MAX,MAX);
    for(int i=1;i<=m;i++){
        for(int k=0;(k+1)*p[i]<MAX;k++){
            mn[(k+1)*p[i]-1]=min(mn[(k+1)*p[i]-1],k*p[i]);
        }
    }
    for(int i=MAX-2;i>=0;i--){
        mn[i]=min(mn[i],mn[i+1]);
    }
    vector<int>ans(MAX);
    for(int i=1;i<MAX;i++){
        if(mn[i]==i||mn[i]==MAX){
            ans[i]=MAX;
        }
        else{
            ans[i]=ans[mn[i]]+1;
        }
    }
    while(q--){
        int n;
        cin>>n;
        if(ans[n]==MAX){
            cout<<"oo\n";
        }
        else{
            cout<<ans[n]<<"\n";
        }
    }
}

Subtask #1

17.7777777778 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	169 ms	156808 KB	Output isn't correct
2	Correct	216 ms	156876 KB	Output is correct
3	Correct	188 ms	156876 KB	Output is correct
4	Correct	173 ms	156844 KB	Output is correct
5	Correct	215 ms	156740 KB	Output is correct
6	Incorrect	183 ms	156804 KB	Output isn't correct
7	Correct	198 ms	156868 KB	Output is correct
8	Correct	213 ms	156748 KB	Output is correct
9	Correct	258 ms	156864 KB	Output is correct
10	Correct	266 ms	156812 KB	Output is correct
11	Correct	293 ms	156808 KB	Output is correct
12	Correct	184 ms	156804 KB	Output is correct
13	Correct	459 ms	156816 KB	Output is correct
14	Correct	455 ms	156868 KB	Output is correct
15	Correct	289 ms	156796 KB	Output is correct
16	Correct	229 ms	156800 KB	Output is correct
17	Correct	222 ms	156848 KB	Output is correct
18	Correct	180 ms	156880 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	157004 KB	Output is correct
2	Correct	218 ms	157872 KB	Output is correct
3	Correct	561 ms	157668 KB	Output is correct
4	Correct	257 ms	156876 KB	Output is correct
5	Correct	385 ms	157356 KB	Output is correct
6	Correct	213 ms	156880 KB	Output is correct
7	Correct	225 ms	156928 KB	Output is correct
8	Correct	245 ms	156788 KB	Output is correct
9	Correct	433 ms	157764 KB	Output is correct
10	Correct	508 ms	157544 KB	Output is correct
11	Correct	497 ms	157212 KB	Output is correct
12	Correct	304 ms	156812 KB	Output is correct
13	Correct	188 ms	156812 KB	Output is correct
14	Correct	236 ms	156832 KB	Output is correct
15	Correct	436 ms	157344 KB	Output is correct
16	Correct	234 ms	157908 KB	Output is correct
17	Correct	434 ms	156836 KB	Output is correct
18	Correct	418 ms	158008 KB	Output is correct

Subtask #3

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	424 ms	157744 KB	Output is correct
2	Correct	513 ms	157620 KB	Output is correct
3	Correct	513 ms	157964 KB	Output is correct
4	Correct	323 ms	157772 KB	Output is correct
5	Correct	255 ms	158908 KB	Output is correct
6	Correct	427 ms	157832 KB	Output is correct
7	Correct	374 ms	158456 KB	Output is correct
8	Correct	435 ms	157804 KB	Output is correct
9	Correct	423 ms	157740 KB	Output is correct
10	Correct	378 ms	157012 KB	Output is correct
11	Correct	298 ms	157056 KB	Output is correct
12	Correct	392 ms	157096 KB	Output is correct
13	Correct	483 ms	158048 KB	Output is correct
14	Correct	302 ms	158108 KB	Output is correct
15	Correct	418 ms	157176 KB	Output is correct
16	Correct	491 ms	157180 KB	Output is correct
17	Correct	423 ms	157388 KB	Output is correct
18	Correct	513 ms	157600 KB	Output is correct
19	Correct	200 ms	157056 KB	Output is correct
20	Correct	523 ms	157964 KB	Output is correct
21	Correct	335 ms	158196 KB	Output is correct
22	Correct	536 ms	158840 KB	Output is correct
23	Correct	250 ms	158284 KB	Output is correct
24	Correct	215 ms	157868 KB	Output is correct
25	Correct	357 ms	157872 KB	Output is correct
26	Correct	314 ms	157856 KB	Output is correct
27	Correct	601 ms	158456 KB	Output is correct
28	Correct	238 ms	157900 KB	Output is correct
29	Correct	485 ms	159024 KB	Output is correct
30	Correct	468 ms	158520 KB	Output is correct
31	Correct	256 ms	157768 KB	Output is correct
32	Correct	273 ms	157860 KB	Output is correct
33	Correct	202 ms	157772 KB	Output is correct
34	Correct	379 ms	158512 KB	Output is correct
35	Correct	237 ms	157908 KB	Output is correct
36	Correct	515 ms	158924 KB	Output is correct
37	Correct	274 ms	158960 KB	Output is correct
38	Correct	436 ms	157832 KB	Output is correct
39	Correct	238 ms	157900 KB	Output is correct
40	Correct	365 ms	157836 KB	Output is correct
41	Correct	336 ms	158504 KB	Output is correct
42	Correct	485 ms	158068 KB	Output is correct