oj.uz

답안 #558897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558897 2022-05-08T23:40:26 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 87 ms 14108 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 = 100000;
    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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1108 KB Output isn't correct
2 Correct 17 ms 1200 KB Output is correct
3 Correct 13 ms 1108 KB Output is correct
4 Correct 5 ms 1200 KB Output is correct
5 Correct 5 ms 1192 KB Output is correct
6 Incorrect 4 ms 1108 KB Output isn't correct
7 Correct 17 ms 1108 KB Output is correct
8 Correct 14 ms 1108 KB Output is correct
9 Correct 17 ms 1192 KB Output is correct
10 Correct 20 ms 1196 KB Output is correct
11 Correct 15 ms 1196 KB Output is correct
12 Correct 4 ms 1108 KB Output is correct
13 Correct 32 ms 1236 KB Output is correct
14 Correct 41 ms 1236 KB Output is correct
15 Correct 14 ms 1108 KB Output is correct
16 Correct 15 ms 1200 KB Output is correct
17 Correct 12 ms 1108 KB Output is correct
18 Correct 8 ms 1108 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 13 ms 3584 KB Execution killed with signal 11
2 Runtime error 48 ms 13080 KB Execution killed with signal 11
3 Runtime error 69 ms 10472 KB Execution killed with signal 11
4 Runtime error 14 ms 2516 KB Execution killed with signal 11
5 Runtime error 48 ms 8332 KB Execution killed with signal 11
6 Runtime error 16 ms 2392 KB Execution killed with signal 11
7 Runtime error 15 ms 3668 KB Execution killed with signal 11
8 Runtime error 13 ms 2292 KB Execution killed with signal 11
9 Runtime error 61 ms 10620 KB Execution killed with signal 11
10 Runtime error 70 ms 10564 KB Execution killed with signal 11
11 Runtime error 64 ms 7020 KB Execution killed with signal 11
12 Runtime error 24 ms 2460 KB Execution killed with signal 11
13 Runtime error 9 ms 2516 KB Execution killed with signal 11
14 Runtime error 14 ms 2532 KB Execution killed with signal 11
15 Runtime error 56 ms 7100 KB Execution killed with signal 11
16 Runtime error 43 ms 13088 KB Execution killed with signal 11
17 Runtime error 39 ms 2524 KB Execution killed with signal 11
18 Runtime error 70 ms 14108 KB Execution killed with signal 11

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 8084 KB Execution killed with signal 11
2 Runtime error 78 ms 8364 KB Execution killed with signal 11
3 Runtime error 66 ms 8092 KB Execution killed with signal 11
4 Runtime error 26 ms 2508 KB Execution killed with signal 11
5 Runtime error 48 ms 13988 KB Execution killed with signal 11
6 Runtime error 36 ms 3072 KB Execution killed with signal 11
7 Runtime error 72 ms 14044 KB Execution killed with signal 11
8 Runtime error 59 ms 8116 KB Execution killed with signal 11
9 Runtime error 57 ms 8092 KB Execution killed with signal 11
10 Runtime error 28 ms 2816 KB Execution killed with signal 11
11 Runtime error 21 ms 2732 KB Execution killed with signal 11
12 Runtime error 34 ms 2820 KB Execution killed with signal 11
13 Runtime error 50 ms 5780 KB Execution killed with signal 11
14 Runtime error 23 ms 2216 KB Execution killed with signal 11
15 Runtime error 39 ms 2852 KB Execution killed with signal 11
16 Runtime error 42 ms 3008 KB Execution killed with signal 11
17 Runtime error 45 ms 7548 KB Execution killed with signal 11
18 Runtime error 65 ms 8360 KB Execution killed with signal 11
19 Runtime error 13 ms 2772 KB Execution killed with signal 11
20 Runtime error 63 ms 8180 KB Execution killed with signal 11
21 Runtime error 26 ms 2220 KB Execution killed with signal 11
22 Runtime error 82 ms 14108 KB Execution killed with signal 11
23 Runtime error 27 ms 5764 KB Execution killed with signal 11
24 Runtime error 12 ms 2288 KB Execution killed with signal 11
25 Runtime error 36 ms 2512 KB Execution killed with signal 11
26 Runtime error 26 ms 2552 KB Execution killed with signal 11
27 Runtime error 87 ms 14044 KB Execution killed with signal 11
28 Runtime error 16 ms 2276 KB Execution killed with signal 11
29 Runtime error 68 ms 14104 KB Execution killed with signal 11
30 Runtime error 57 ms 10556 KB Execution killed with signal 11
31 Runtime error 13 ms 2728 KB Execution killed with signal 11
32 Runtime error 15 ms 2524 KB Execution killed with signal 11
33 Runtime error 6 ms 2388 KB Execution killed with signal 11
34 Runtime error 63 ms 14060 KB Execution killed with signal 11
35 Runtime error 13 ms 2464 KB Execution killed with signal 11
36 Runtime error 75 ms 12920 KB Execution killed with signal 11
37 Runtime error 57 ms 13904 KB Execution killed with signal 11
38 Runtime error 39 ms 3188 KB Execution killed with signal 11
39 Runtime error 10 ms 2388 KB Execution killed with signal 11
40 Runtime error 46 ms 3272 KB Execution killed with signal 11
41 Runtime error 67 ms 14108 KB Execution killed with signal 11
42 Runtime error 39 ms 2516 KB Execution killed with signal 11