oj.uz

답안 #558899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558899 2022-05-08T23:44:59 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 130 ms 15532 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];
    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:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 1876 KB Output isn't correct
2 Correct 30 ms 1876 KB Output is correct
3 Correct 22 ms 1876 KB Output is correct
4 Correct 8 ms 1876 KB Output is correct
5 Correct 10 ms 1876 KB Output is correct
6 Incorrect 7 ms 1876 KB Output isn't correct
7 Correct 20 ms 1876 KB Output is correct
8 Correct 28 ms 1876 KB Output is correct
9 Correct 34 ms 1876 KB Output is correct
10 Correct 37 ms 1876 KB Output is correct
11 Correct 29 ms 1876 KB Output is correct
12 Correct 5 ms 1876 KB Output is correct
13 Correct 76 ms 1920 KB Output is correct
14 Correct 67 ms 1920 KB Output is correct
15 Correct 28 ms 1880 KB Output is correct
16 Correct 30 ms 1888 KB Output is correct
17 Correct 14 ms 1884 KB Output is correct
18 Correct 8 ms 1876 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 5016 KB Execution killed with signal 11
2 Runtime error 50 ms 14456 KB Execution killed with signal 11
3 Runtime error 113 ms 11920 KB Execution killed with signal 11
4 Runtime error 27 ms 3900 KB Execution killed with signal 11
5 Runtime error 69 ms 9688 KB Execution killed with signal 11
6 Runtime error 30 ms 3704 KB Execution killed with signal 11
7 Runtime error 18 ms 5016 KB Execution killed with signal 11
8 Runtime error 23 ms 3672 KB Execution killed with signal 11
9 Runtime error 90 ms 12164 KB Execution killed with signal 11
10 Runtime error 112 ms 11880 KB Execution killed with signal 11
11 Runtime error 97 ms 8340 KB Execution killed with signal 11
12 Runtime error 47 ms 3804 KB Execution killed with signal 11
13 Runtime error 22 ms 3944 KB Execution killed with signal 11
14 Runtime error 25 ms 3948 KB Execution killed with signal 11
15 Runtime error 91 ms 8492 KB Execution killed with signal 11
16 Runtime error 55 ms 14404 KB Execution killed with signal 11
17 Runtime error 71 ms 3960 KB Execution killed with signal 11
18 Runtime error 103 ms 15476 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 91 ms 9552 KB Execution killed with signal 11
2 Runtime error 105 ms 9816 KB Execution killed with signal 11
3 Runtime error 108 ms 9552 KB Execution killed with signal 11
4 Runtime error 48 ms 3916 KB Execution killed with signal 11
5 Runtime error 56 ms 15308 KB Execution killed with signal 11
6 Runtime error 67 ms 4528 KB Execution killed with signal 11
7 Runtime error 82 ms 15532 KB Execution killed with signal 11
8 Runtime error 94 ms 9544 KB Execution killed with signal 11
9 Runtime error 95 ms 9540 KB Execution killed with signal 11
10 Runtime error 51 ms 4276 KB Execution killed with signal 11
11 Runtime error 41 ms 4044 KB Execution killed with signal 11
12 Runtime error 64 ms 4268 KB Execution killed with signal 11
13 Runtime error 87 ms 7104 KB Execution killed with signal 11
14 Runtime error 50 ms 3536 KB Execution killed with signal 11
15 Runtime error 78 ms 4248 KB Execution killed with signal 11
16 Runtime error 81 ms 4456 KB Execution killed with signal 11
17 Runtime error 75 ms 8888 KB Execution killed with signal 11
18 Runtime error 107 ms 9820 KB Execution killed with signal 11
19 Runtime error 23 ms 4232 KB Execution killed with signal 11
20 Runtime error 105 ms 9548 KB Execution killed with signal 11
21 Runtime error 53 ms 3532 KB Execution killed with signal 11
22 Runtime error 122 ms 15452 KB Execution killed with signal 11
23 Runtime error 32 ms 7116 KB Execution killed with signal 11
24 Runtime error 14 ms 3736 KB Execution killed with signal 11
25 Runtime error 48 ms 3840 KB Execution killed with signal 11
26 Runtime error 50 ms 3980 KB Execution killed with signal 11
27 Runtime error 130 ms 15432 KB Execution killed with signal 11
28 Runtime error 23 ms 3724 KB Execution killed with signal 11
29 Runtime error 101 ms 15504 KB Execution killed with signal 11
30 Runtime error 79 ms 11872 KB Execution killed with signal 11
31 Runtime error 26 ms 4060 KB Execution killed with signal 11
32 Runtime error 29 ms 3836 KB Execution killed with signal 11
33 Runtime error 11 ms 3744 KB Execution killed with signal 11
34 Runtime error 81 ms 15484 KB Execution killed with signal 11
35 Runtime error 22 ms 3800 KB Execution killed with signal 11
36 Runtime error 120 ms 14332 KB Execution killed with signal 11
37 Runtime error 55 ms 15308 KB Execution killed with signal 11
38 Runtime error 67 ms 4524 KB Execution killed with signal 11
39 Runtime error 18 ms 3844 KB Execution killed with signal 11
40 Runtime error 62 ms 4728 KB Execution killed with signal 11
41 Runtime error 89 ms 15512 KB Execution killed with signal 11
42 Runtime error 75 ms 3956 KB Execution killed with signal 11