oj.uz

Submission #558895

# Submission time Handle Problem Language Result Execution time Memory
558895 2022-05-08T23:39:38 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 48 ms 12612 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 = 10;
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Runtime error 1 ms 340 KB Execution killed with signal 11
4 Runtime error 1 ms 504 KB Execution killed with signal 11
5 Incorrect 1 ms 320 KB Output isn't correct
6 Runtime error 1 ms 468 KB Execution killed with signal 11
7 Runtime error 1 ms 468 KB Execution killed with signal 11
8 Runtime error 1 ms 448 KB Execution killed with signal 11
9 Runtime error 1 ms 340 KB Execution killed with signal 11
10 Runtime error 1 ms 452 KB Execution killed with signal 11
11 Runtime error 1 ms 468 KB Execution killed with signal 11
12 Runtime error 1 ms 468 KB Execution killed with signal 11
13 Runtime error 1 ms 468 KB Execution killed with signal 11
14 Runtime error 1 ms 596 KB Execution killed with signal 11
15 Runtime error 1 ms 452 KB Execution killed with signal 11
16 Runtime error 2 ms 468 KB Execution killed with signal 11
17 Runtime error 3 ms 468 KB Execution killed with signal 11
18 Runtime error 1 ms 468 KB Execution killed with signal 11

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1864 KB Execution killed with signal 11
2 Runtime error 36 ms 11536 KB Execution killed with signal 11
3 Runtime error 29 ms 8852 KB Execution killed with signal 11
4 Runtime error 2 ms 852 KB Execution killed with signal 11
5 Runtime error 21 ms 6604 KB Execution killed with signal 11
6 Runtime error 3 ms 580 KB Execution killed with signal 11
7 Runtime error 5 ms 1960 KB Execution killed with signal 11
8 Runtime error 1 ms 468 KB Execution killed with signal 11
9 Runtime error 28 ms 8996 KB Execution killed with signal 11
10 Runtime error 29 ms 8844 KB Execution killed with signal 11
11 Runtime error 16 ms 5316 KB Execution killed with signal 11
12 Runtime error 3 ms 716 KB Execution killed with signal 11
13 Runtime error 3 ms 764 KB Execution killed with signal 11
14 Runtime error 2 ms 852 KB Execution killed with signal 11
15 Runtime error 17 ms 5524 KB Execution killed with signal 11
16 Runtime error 36 ms 11496 KB Execution killed with signal 11
17 Runtime error 2 ms 724 KB Execution killed with signal 11
18 Runtime error 40 ms 12588 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 24 ms 6428 KB Execution killed with signal 11
2 Runtime error 19 ms 6740 KB Execution killed with signal 11
3 Runtime error 22 ms 6508 KB Execution killed with signal 11
4 Runtime error 3 ms 980 KB Execution killed with signal 11
5 Runtime error 44 ms 12448 KB Execution killed with signal 11
6 Runtime error 4 ms 1492 KB Execution killed with signal 11
7 Runtime error 42 ms 12596 KB Execution killed with signal 11
8 Runtime error 20 ms 6476 KB Execution killed with signal 11
9 Runtime error 19 ms 6468 KB Execution killed with signal 11
10 Runtime error 3 ms 1236 KB Execution killed with signal 11
11 Runtime error 2 ms 1108 KB Execution killed with signal 11
12 Runtime error 3 ms 1236 KB Execution killed with signal 11
13 Runtime error 11 ms 4080 KB Execution killed with signal 11
14 Runtime error 1 ms 468 KB Execution killed with signal 11
15 Runtime error 3 ms 1108 KB Execution killed with signal 11
16 Runtime error 3 ms 1504 KB Execution killed with signal 11
17 Runtime error 18 ms 5912 KB Execution killed with signal 11
18 Runtime error 22 ms 6740 KB Execution killed with signal 11
19 Runtime error 3 ms 1096 KB Execution killed with signal 11
20 Runtime error 20 ms 6484 KB Execution killed with signal 11
21 Runtime error 1 ms 468 KB Execution killed with signal 11
22 Runtime error 45 ms 12256 KB Execution killed with signal 11
23 Runtime error 12 ms 4052 KB Execution killed with signal 11
24 Runtime error 2 ms 596 KB Execution killed with signal 11
25 Runtime error 3 ms 724 KB Execution killed with signal 11
26 Runtime error 2 ms 980 KB Execution killed with signal 11
27 Runtime error 40 ms 12612 KB Execution killed with signal 11
28 Runtime error 1 ms 596 KB Execution killed with signal 11
29 Runtime error 40 ms 12548 KB Execution killed with signal 11
30 Runtime error 32 ms 8900 KB Execution killed with signal 11
31 Runtime error 3 ms 1108 KB Execution killed with signal 11
32 Runtime error 2 ms 852 KB Execution killed with signal 11
33 Runtime error 1 ms 588 KB Execution killed with signal 11
34 Runtime error 48 ms 12580 KB Execution killed with signal 11
35 Runtime error 2 ms 724 KB Execution killed with signal 11
36 Runtime error 38 ms 11356 KB Execution killed with signal 11
37 Runtime error 48 ms 12584 KB Execution killed with signal 11
38 Runtime error 4 ms 1492 KB Execution killed with signal 11
39 Runtime error 2 ms 840 KB Execution killed with signal 11
40 Runtime error 4 ms 1620 KB Execution killed with signal 11
41 Runtime error 44 ms 12508 KB Execution killed with signal 11
42 Runtime error 2 ms 852 KB Execution killed with signal 11