Submission #558904

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
558904	2022-05-08T23:52:11 Z	Olympia	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	13.1746 / 100	1000 ms	84060 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int M, Q; cin >> M >> Q;
    vector<int> p(M);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end()); 
    int mx = 10000000;
    int res[mx];
    int lpf[mx];
    for (int i = 0; i < mx; i++) {
        lpf[i] = -1;
    }
    for (int j = 0; j < p.size(); j++) {
        for (int i = p[j]; i < mx; i += p[j]) {
            lpf[i] = j;
        }
    }
    int dp[M];
    multiset<int> ms;
    for (int i = 0; i < M; i++) {
        dp[i] = 0;
        ms.insert(dp[i]);
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        if (lpf[i] == -1) {
            ans = *ms.begin() + 1;
        } else {
            vector<int> invalid;
            int x = i;
            while (lpf[x] != -1) {
                invalid.push_back(lpf[x]);
                int a = p[lpf[x]];
                while (x % a == 0) x /= a;
            }
            for (int j: invalid) {
                ms.erase(ms.find(dp[j]));
            }
            if (!ms.empty()) {
                ans = *ms.begin() + 1;
            }
            for (int j: invalid) {
                ms.insert(dp[j]);
            }
            for (int j: invalid) {
                if (j >= 0 && j < (int)p.size()) {
                    ms.erase(ms.find(dp[j]));
                    dp[j] = ans;
                    ms.insert(dp[j]);
                }
            }
        }
        res[i] = ans;
    }
    while (Q--) {
        int x;
        cin >> x;
        if (res[x] == (int)1e9) {
            cout << "oo\n";
        } else {
            cout << res[x] << '\n';
        }
    }
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.55555555556 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	314 ms	78576 KB	Output isn't correct
2	Execution timed out	1087 ms	78592 KB	Time limit exceeded
3	Execution timed out	1088 ms	78440 KB	Time limit exceeded
4	Correct	262 ms	78580 KB	Output is correct
5	Correct	611 ms	78568 KB	Output is correct
6	Incorrect	305 ms	78572 KB	Output isn't correct
7	Execution timed out	1097 ms	78556 KB	Time limit exceeded
8	Execution timed out	1094 ms	78508 KB	Time limit exceeded
9	Execution timed out	1095 ms	78488 KB	Time limit exceeded
10	Execution timed out	1084 ms	78548 KB	Time limit exceeded
11	Execution timed out	1084 ms	78528 KB	Time limit exceeded
12	Correct	216 ms	78540 KB	Output is correct
13	Execution timed out	1093 ms	78584 KB	Time limit exceeded
14	Execution timed out	1096 ms	78576 KB	Time limit exceeded
15	Execution timed out	1099 ms	78464 KB	Time limit exceeded
16	Execution timed out	1094 ms	78572 KB	Time limit exceeded
17	Correct	814 ms	78572 KB	Output is correct
18	Correct	256 ms	78580 KB	Output is correct

Subtask #2
3.33333333333 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	807 ms	79356 KB	Output is correct
2	Execution timed out	1081 ms	83552 KB	Time limit exceeded
3	Execution timed out	1092 ms	82332 KB	Time limit exceeded
4	Execution timed out	1085 ms	78668 KB	Time limit exceeded
5	Execution timed out	1078 ms	81336 KB	Time limit exceeded
6	Execution timed out	1094 ms	78548 KB	Time limit exceeded
7	Correct	774 ms	79228 KB	Output is correct
8	Execution timed out	1091 ms	78576 KB	Time limit exceeded
9	Execution timed out	1070 ms	82412 KB	Time limit exceeded
10	Execution timed out	1093 ms	82300 KB	Time limit exceeded
11	Execution timed out	1091 ms	80668 KB	Time limit exceeded
12	Execution timed out	1085 ms	78584 KB	Time limit exceeded
13	Correct	977 ms	78732 KB	Output is correct
14	Execution timed out	1086 ms	78668 KB	Time limit exceeded
15	Execution timed out	1096 ms	80796 KB	Time limit exceeded
16	Execution timed out	1098 ms	83660 KB	Time limit exceeded
17	Execution timed out	1093 ms	78708 KB	Time limit exceeded
18	Execution timed out	1097 ms	84044 KB	Time limit exceeded

Subtask #3
4.28571428571 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1091 ms	81240 KB	Time limit exceeded
2	Execution timed out	1088 ms	81352 KB	Time limit exceeded
3	Execution timed out	1099 ms	81212 KB	Time limit exceeded
4	Execution timed out	1098 ms	78796 KB	Time limit exceeded
5	Execution timed out	1096 ms	83976 KB	Time limit exceeded
6	Execution timed out	1091 ms	79000 KB	Time limit exceeded
7	Execution timed out	1094 ms	84044 KB	Time limit exceeded
8	Execution timed out	1104 ms	81324 KB	Time limit exceeded
9	Execution timed out	1056 ms	81212 KB	Time limit exceeded
10	Execution timed out	1082 ms	78848 KB	Time limit exceeded
11	Execution timed out	1072 ms	78720 KB	Time limit exceeded
12	Execution timed out	1071 ms	78796 KB	Time limit exceeded
13	Execution timed out	1084 ms	80204 KB	Time limit exceeded
14	Execution timed out	1101 ms	78460 KB	Time limit exceeded
15	Execution timed out	1102 ms	78852 KB	Time limit exceeded
16	Execution timed out	1086 ms	78856 KB	Time limit exceeded
17	Execution timed out	1098 ms	80932 KB	Time limit exceeded
18	Execution timed out	1090 ms	81352 KB	Time limit exceeded
19	Execution timed out	1073 ms	78912 KB	Time limit exceeded
20	Execution timed out	1089 ms	81280 KB	Time limit exceeded
21	Execution timed out	1093 ms	78580 KB	Time limit exceeded
22	Execution timed out	1097 ms	83952 KB	Time limit exceeded
23	Execution timed out	1092 ms	80100 KB	Time limit exceeded
24	Correct	706 ms	78888 KB	Output is correct
25	Execution timed out	1103 ms	78712 KB	Time limit exceeded
26	Execution timed out	1102 ms	78720 KB	Time limit exceeded
27	Execution timed out	1101 ms	84044 KB	Time limit exceeded
28	Execution timed out	1097 ms	78540 KB	Time limit exceeded
29	Execution timed out	1101 ms	84060 KB	Time limit exceeded
30	Execution timed out	1101 ms	82348 KB	Time limit exceeded
31	Execution timed out	1091 ms	78792 KB	Time limit exceeded
32	Execution timed out	1083 ms	78700 KB	Time limit exceeded
33	Correct	452 ms	78864 KB	Output is correct
34	Execution timed out	1093 ms	83968 KB	Time limit exceeded
35	Execution timed out	1096 ms	78672 KB	Time limit exceeded
36	Execution timed out	1092 ms	83404 KB	Time limit exceeded
37	Execution timed out	1086 ms	84044 KB	Time limit exceeded
38	Execution timed out	1097 ms	79000 KB	Time limit exceeded
39	Correct	934 ms	78956 KB	Output is correct
40	Execution timed out	1064 ms	78992 KB	Time limit exceeded
41	Execution timed out	1089 ms	83968 KB	Time limit exceeded
42	Execution timed out	1090 ms	78712 KB	Time limit exceeded

Submission #558904

Compilation message

Subtask #1 5.55555555556 / 20.0

Subtask #2 3.33333333333 / 20.0

Subtask #3 4.28571428571 / 60.0

Subtask #1
5.55555555556 / 20.0

Subtask #2
3.33333333333 / 20.0

Subtask #3
4.28571428571 / 60.0