Submission #283099

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
283099	2020-08-25T09:59:07 Z	egekabas	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	5.55556 / 100	1000 ms	38520 KB

brunhilda

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, q;
int p[100009];
int ans[10000001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    srand(time(NULL));
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> q;
    for(int i = 0; i < n; ++i)
        cin >> p[i];
    reverse(p, p+n);
    ans[0] = 0;
    int lim = 1e7+1;
    for(int i = 1; i < lim; ++i){
        int goback = -1;
        for(int j = 0; j < min(n, 5); ++j)
            goback = max(goback, i%p[j]);
        int cnt = 5;
        while(cnt--){
            int j = rand()%n;
            goback = max(goback, i%p[j]);    
        }

        if(goback == 0){
            lim = i;
            break;
        }
        ans[i] = 1+ans[i-goback];
    }
    while(q--){
        int x;
        cin >> x;
        if(x >= lim)
            cout << "oo\n";
        else
            cout << ans[x] << '\n';
    }
}

Subtask #1
5.55555555556 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Execution timed out	1095 ms	31452 KB	Time limit exceeded
3	Correct	38 ms	1400 KB	Output is correct
4	Execution timed out	1088 ms	32944 KB	Time limit exceeded
5	Execution timed out	1092 ms	31408 KB	Time limit exceeded
6	Correct	2 ms	384 KB	Output is correct
7	Correct	55 ms	1404 KB	Output is correct
8	Correct	129 ms	3936 KB	Output is correct
9	Execution timed out	1058 ms	29668 KB	Time limit exceeded
10	Execution timed out	1089 ms	30796 KB	Time limit exceeded
11	Execution timed out	1093 ms	30960 KB	Time limit exceeded
12	Execution timed out	1088 ms	33460 KB	Time limit exceeded
13	Execution timed out	1075 ms	32756 KB	Time limit exceeded
14	Execution timed out	1088 ms	34884 KB	Time limit exceeded
15	Execution timed out	1089 ms	31628 KB	Time limit exceeded
16	Execution timed out	1079 ms	31000 KB	Time limit exceeded
17	Execution timed out	1083 ms	28664 KB	Time limit exceeded
18	Execution timed out	1062 ms	31788 KB	Time limit exceeded

Subtask #2
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1078 ms	32380 KB	Time limit exceeded
2	Execution timed out	1077 ms	32436 KB	Time limit exceeded
3	Execution timed out	1093 ms	33552 KB	Time limit exceeded
4	Execution timed out	1089 ms	35876 KB	Time limit exceeded
5	Execution timed out	1045 ms	31056 KB	Time limit exceeded
6	Execution timed out	1081 ms	37088 KB	Time limit exceeded
7	Execution timed out	1062 ms	34324 KB	Time limit exceeded
8	Execution timed out	1052 ms	34356 KB	Time limit exceeded
9	Execution timed out	1064 ms	28464 KB	Time limit exceeded
10	Execution timed out	1061 ms	33828 KB	Time limit exceeded
11	Execution timed out	1050 ms	33016 KB	Time limit exceeded
12	Execution timed out	1091 ms	35776 KB	Time limit exceeded
13	Execution timed out	1096 ms	34136 KB	Time limit exceeded
14	Execution timed out	1095 ms	36700 KB	Time limit exceeded
15	Execution timed out	1081 ms	33804 KB	Time limit exceeded
16	Execution timed out	1099 ms	33040 KB	Time limit exceeded
17	Execution timed out	1095 ms	33892 KB	Time limit exceeded
18	Execution timed out	1099 ms	35376 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1097 ms	34296 KB	Time limit exceeded
2	Execution timed out	1095 ms	28904 KB	Time limit exceeded
3	Execution timed out	1064 ms	32108 KB	Time limit exceeded
4	Execution timed out	1080 ms	31144 KB	Time limit exceeded
5	Execution timed out	1097 ms	29928 KB	Time limit exceeded
6	Execution timed out	1096 ms	35780 KB	Time limit exceeded
7	Execution timed out	1052 ms	29160 KB	Time limit exceeded
8	Execution timed out	1089 ms	33692 KB	Time limit exceeded
9	Execution timed out	1089 ms	34260 KB	Time limit exceeded
10	Execution timed out	1072 ms	32868 KB	Time limit exceeded
11	Execution timed out	1093 ms	32504 KB	Time limit exceeded
12	Execution timed out	1073 ms	33392 KB	Time limit exceeded
13	Execution timed out	1099 ms	31864 KB	Time limit exceeded
14	Execution timed out	1093 ms	31352 KB	Time limit exceeded
15	Execution timed out	1100 ms	35064 KB	Time limit exceeded
16	Execution timed out	1089 ms	34796 KB	Time limit exceeded
17	Execution timed out	1060 ms	30208 KB	Time limit exceeded
18	Execution timed out	1091 ms	33144 KB	Time limit exceeded
19	Execution timed out	1092 ms	38068 KB	Time limit exceeded
20	Execution timed out	1092 ms	35232 KB	Time limit exceeded
21	Execution timed out	1046 ms	31336 KB	Time limit exceeded
22	Execution timed out	1098 ms	29748 KB	Time limit exceeded
23	Execution timed out	1097 ms	35592 KB	Time limit exceeded
24	Execution timed out	1094 ms	37708 KB	Time limit exceeded
25	Execution timed out	1091 ms	36012 KB	Time limit exceeded
26	Execution timed out	1100 ms	37496 KB	Time limit exceeded
27	Execution timed out	1072 ms	32632 KB	Time limit exceeded
28	Execution timed out	1096 ms	37496 KB	Time limit exceeded
29	Execution timed out	1098 ms	31352 KB	Time limit exceeded
30	Execution timed out	1059 ms	32300 KB	Time limit exceeded
31	Execution timed out	1100 ms	37880 KB	Time limit exceeded
32	Execution timed out	1095 ms	37488 KB	Time limit exceeded
33	Execution timed out	1100 ms	38520 KB	Time limit exceeded
34	Execution timed out	1095 ms	32228 KB	Time limit exceeded
35	Execution timed out	1101 ms	37624 KB	Time limit exceeded
36	Execution timed out	1091 ms	29712 KB	Time limit exceeded
37	Execution timed out	1100 ms	30072 KB	Time limit exceeded
38	Execution timed out	1086 ms	34760 KB	Time limit exceeded
39	Execution timed out	1067 ms	34868 KB	Time limit exceeded
40	Execution timed out	1093 ms	34884 KB	Time limit exceeded
41	Execution timed out	1098 ms	33748 KB	Time limit exceeded
42	Execution timed out	1079 ms	34808 KB	Time limit exceeded

Submission #283099

Compilation message

Subtask #1 5.55555555556 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
5.55555555556 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0