oj.uz

Submission #558898

# Submission time Handle Problem Language Result Execution time Memory
558898 2022-05-08T23:41:30 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 125 ms 15896 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 = 200000;
    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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2004 KB Output isn't correct
2 Correct 32 ms 2080 KB Output is correct
3 Correct 23 ms 2068 KB Output is correct
4 Correct 7 ms 2004 KB Output is correct
5 Correct 10 ms 2004 KB Output is correct
6 Incorrect 7 ms 2004 KB Output isn't correct
7 Correct 21 ms 2004 KB Output is correct
8 Correct 27 ms 2052 KB Output is correct
9 Correct 33 ms 2004 KB Output is correct
10 Correct 36 ms 2004 KB Output is correct
11 Correct 28 ms 2004 KB Output is correct
12 Correct 6 ms 2080 KB Output is correct
13 Correct 64 ms 2112 KB Output is correct
14 Correct 65 ms 2132 KB Output is correct
15 Correct 27 ms 2004 KB Output is correct
16 Correct 28 ms 2080 KB Output is correct
17 Correct 14 ms 2080 KB Output is correct
18 Correct 7 ms 2004 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 5348 KB Execution killed with signal 11
2 Runtime error 52 ms 14796 KB Execution killed with signal 11
3 Runtime error 111 ms 12332 KB Execution killed with signal 11
4 Runtime error 26 ms 4308 KB Execution killed with signal 11
5 Runtime error 68 ms 10072 KB Execution killed with signal 11
6 Runtime error 29 ms 4060 KB Execution killed with signal 11
7 Runtime error 18 ms 5344 KB Execution killed with signal 11
8 Runtime error 22 ms 4060 KB Execution killed with signal 11
9 Runtime error 92 ms 12400 KB Execution killed with signal 11
10 Runtime error 112 ms 12328 KB Execution killed with signal 11
11 Runtime error 103 ms 8784 KB Execution killed with signal 11
12 Runtime error 44 ms 4240 KB Execution killed with signal 11
13 Runtime error 17 ms 4296 KB Execution killed with signal 11
14 Runtime error 25 ms 4308 KB Execution killed with signal 11
15 Runtime error 84 ms 8892 KB Execution killed with signal 11
16 Runtime error 54 ms 15152 KB Execution killed with signal 11
17 Runtime error 70 ms 4284 KB Execution killed with signal 11
18 Runtime error 98 ms 15880 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 9936 KB Execution killed with signal 11
2 Runtime error 104 ms 10272 KB Execution killed with signal 11
3 Runtime error 106 ms 9932 KB Execution killed with signal 11
4 Runtime error 47 ms 4300 KB Execution killed with signal 11
5 Runtime error 56 ms 15712 KB Execution killed with signal 11
6 Runtime error 66 ms 4980 KB Execution killed with signal 11
7 Runtime error 80 ms 15884 KB Execution killed with signal 11
8 Runtime error 90 ms 9932 KB Execution killed with signal 11
9 Runtime error 89 ms 9960 KB Execution killed with signal 11
10 Runtime error 47 ms 4592 KB Execution killed with signal 11
11 Runtime error 36 ms 4504 KB Execution killed with signal 11
12 Runtime error 64 ms 4592 KB Execution killed with signal 11
13 Runtime error 86 ms 7544 KB Execution killed with signal 11
14 Runtime error 41 ms 3992 KB Execution killed with signal 11
15 Runtime error 71 ms 4568 KB Execution killed with signal 11
16 Runtime error 81 ms 4792 KB Execution killed with signal 11
17 Runtime error 72 ms 9324 KB Execution killed with signal 11
18 Runtime error 108 ms 10188 KB Execution killed with signal 11
19 Runtime error 23 ms 4528 KB Execution killed with signal 11
20 Runtime error 102 ms 9912 KB Execution killed with signal 11
21 Runtime error 51 ms 4000 KB Execution killed with signal 11
22 Runtime error 122 ms 15896 KB Execution killed with signal 11
23 Runtime error 29 ms 7568 KB Execution killed with signal 11
24 Runtime error 16 ms 4064 KB Execution killed with signal 11
25 Runtime error 48 ms 4292 KB Execution killed with signal 11
26 Runtime error 48 ms 4316 KB Execution killed with signal 11
27 Runtime error 125 ms 15840 KB Execution killed with signal 11
28 Runtime error 20 ms 4048 KB Execution killed with signal 11
29 Runtime error 96 ms 15876 KB Execution killed with signal 11
30 Runtime error 82 ms 12364 KB Execution killed with signal 11
31 Runtime error 24 ms 4504 KB Execution killed with signal 11
32 Runtime error 28 ms 4300 KB Execution killed with signal 11
33 Runtime error 11 ms 4052 KB Execution killed with signal 11
34 Runtime error 84 ms 15820 KB Execution killed with signal 11
35 Runtime error 22 ms 4240 KB Execution killed with signal 11
36 Runtime error 112 ms 14660 KB Execution killed with signal 11
37 Runtime error 54 ms 15724 KB Execution killed with signal 11
38 Runtime error 68 ms 4844 KB Execution killed with signal 11
39 Runtime error 17 ms 4260 KB Execution killed with signal 11
40 Runtime error 58 ms 5068 KB Execution killed with signal 11
41 Runtime error 89 ms 15844 KB Execution killed with signal 11
42 Runtime error 75 ms 4276 KB Execution killed with signal 11