oj.uz

Submission #558896

# Submission time Handle Problem Language Result Execution time Memory
558896 2022-05-08T23:40:02 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
15.3968 / 100
 1000 ms 94972 KB 
#include <bits/stdc++.h>
using namespace std;
template<class T> struct Seg { // comb(ID,b) = b
	const T ID = 1e9; T comb(T a, T b) { return min(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// min on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int M, Q; cin >> M >> Q;
    vector<int> p(M);
    Seg<int> st;
    st.init(M + 1);
    map<int,int> primes;
    for (int i = 0; i < M; i++) {
        cin >> p[i];
        st.upd(i, 0);
    }
    sort(p.begin(), p.end());
    for (int i = 0; i < M; i++) {
        primes[p[i]] = i;
        st.upd(i, 0);
    } 
    int mx = 10000000;
    int res[mx];
    bool isPrime[mx];
    for (int i = 0; i < mx; i++) {
        isPrime[i] = true;
    }
    isPrime[0] = isPrime[1] = false;
    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;
        }
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        if (lpf[i] == -1) {
            ans = st.query(0, M - 1) + 1;
        } else {
            vector<int> invalid;
            invalid.push_back(-1);
            int x = i;
            while (lpf[x] != -1) {
                invalid.push_back(lpf[x]);
                int a = p[lpf[x]];
                while (x % a == 0) x /= a;
            }
            sort(invalid.begin(), invalid.end());
            invalid.push_back(p.size());
            for (int j = 0; j < (int)invalid.size() - 1; j++) {
                if (invalid[j] + 1 <= invalid[j + 1] - 1) {
                    ans = min(ans, st.query(invalid[j] + 1, invalid[j + 1] - 1) + 1);
                }
            }
            for (int j: invalid) {
                if (j >= 0 && j < (int)p.size()) {
                    st.upd(j, ans);
                }
            }
        }
        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:47:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 344 ms 88356 KB Output isn't correct
2 Execution timed out 1089 ms 88316 KB Time limit exceeded
3 Execution timed out 1088 ms 88268 KB Time limit exceeded
4 Correct 312 ms 88276 KB Output is correct
5 Correct 533 ms 88352 KB Output is correct
6 Incorrect 308 ms 88356 KB Output isn't correct
7 Execution timed out 1040 ms 88356 KB Time limit exceeded
8 Execution timed out 1093 ms 88352 KB Time limit exceeded
9 Execution timed out 1080 ms 88276 KB Time limit exceeded
10 Execution timed out 1096 ms 88236 KB Time limit exceeded
11 Execution timed out 1084 ms 88396 KB Time limit exceeded
12 Correct 318 ms 88356 KB Output is correct
13 Execution timed out 1097 ms 88332 KB Time limit exceeded
14 Execution timed out 1098 ms 88404 KB Time limit exceeded
15 Execution timed out 1088 ms 88268 KB Time limit exceeded
16 Execution timed out 1079 ms 88236 KB Time limit exceeded
17 Correct 629 ms 88364 KB Output is correct
18 Correct 313 ms 88364 KB Output is correct

Subtask #2
5.55555555556 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 89064 KB Output is correct
2 Correct 928 ms 93772 KB Output is correct
3 Execution timed out 1103 ms 92364 KB Time limit exceeded
4 Execution timed out 1096 ms 88456 KB Time limit exceeded
5 Execution timed out 1074 ms 91360 KB Time limit exceeded
6 Execution timed out 1091 ms 88396 KB Time limit exceeded
7 Correct 730 ms 89068 KB Output is correct
8 Execution timed out 1097 ms 88400 KB Time limit exceeded
9 Execution timed out 1096 ms 92504 KB Time limit exceeded
10 Execution timed out 1106 ms 92416 KB Time limit exceeded
11 Execution timed out 1094 ms 90696 KB Time limit exceeded
12 Execution timed out 1088 ms 88384 KB Time limit exceeded
13 Correct 823 ms 88532 KB Output is correct
14 Execution timed out 1089 ms 88468 KB Time limit exceeded
15 Execution timed out 1087 ms 90824 KB Time limit exceeded
16 Correct 914 ms 93740 KB Output is correct
17 Execution timed out 1099 ms 88524 KB Time limit exceeded
18 Execution timed out 1094 ms 94248 KB Time limit exceeded

Subtask #3
4.28571428571 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 91212 KB Time limit exceeded
2 Execution timed out 1094 ms 91340 KB Time limit exceeded
3 Execution timed out 1084 ms 91216 KB Time limit exceeded
4 Execution timed out 1093 ms 88480 KB Time limit exceeded
5 Execution timed out 1095 ms 94336 KB Time limit exceeded
6 Execution timed out 1102 ms 88780 KB Time limit exceeded
7 Execution timed out 1105 ms 94116 KB Time limit exceeded
8 Execution timed out 1105 ms 91208 KB Time limit exceeded
9 Execution timed out 1101 ms 91220 KB Time limit exceeded
10 Execution timed out 1096 ms 88652 KB Time limit exceeded
11 Execution timed out 1090 ms 88504 KB Time limit exceeded
12 Execution timed out 1097 ms 88652 KB Time limit exceeded
13 Execution timed out 1097 ms 90100 KB Time limit exceeded
14 Execution timed out 1093 ms 88348 KB Time limit exceeded
15 Execution timed out 1066 ms 88604 KB Time limit exceeded
16 Execution timed out 1101 ms 88764 KB Time limit exceeded
17 Execution timed out 1086 ms 91004 KB Time limit exceeded
18 Execution timed out 1100 ms 91532 KB Time limit exceeded
19 Execution timed out 1044 ms 88788 KB Time limit exceeded
20 Execution timed out 1090 ms 91288 KB Time limit exceeded
21 Execution timed out 1102 ms 88328 KB Time limit exceeded
22 Execution timed out 1095 ms 94236 KB Time limit exceeded
23 Execution timed out 1089 ms 90260 KB Time limit exceeded
24 Correct 603 ms 89140 KB Output is correct
25 Execution timed out 1095 ms 88508 KB Time limit exceeded
26 Execution timed out 1096 ms 88480 KB Time limit exceeded
27 Execution timed out 1097 ms 94456 KB Time limit exceeded
28 Incorrect 878 ms 89444 KB Output isn't correct
29 Execution timed out 1090 ms 94284 KB Time limit exceeded
30 Execution timed out 1092 ms 92420 KB Time limit exceeded
31 Execution timed out 1079 ms 89420 KB Time limit exceeded
32 Execution timed out 1100 ms 88512 KB Time limit exceeded
33 Correct 459 ms 88564 KB Output is correct
34 Execution timed out 1095 ms 94184 KB Time limit exceeded
35 Incorrect 989 ms 89420 KB Output isn't correct
36 Execution timed out 1094 ms 93612 KB Time limit exceeded
37 Execution timed out 1089 ms 94972 KB Time limit exceeded
38 Execution timed out 1100 ms 88760 KB Time limit exceeded
39 Correct 759 ms 89352 KB Output is correct
40 Execution timed out 1102 ms 88836 KB Time limit exceeded
41 Execution timed out 1097 ms 94156 KB Time limit exceeded
42 Execution timed out 1102 ms 88472 KB Time limit exceeded