oj.uz

답안 #558894

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
558894 2022-05-08T23:38:33 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
6.98413 / 100
 1000 ms 94376 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 i = 2; i < mx; i++) {
        if (isPrime[i]) {
            for (int j = 2 * i; j < mx; j += i) {
                isPrime[j] = false;
                if (primes.count(i)) lpf[j] = primes[i];
            }
            if (primes.count(i)) lpf[i] = primes[i];
        }
    }
    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';
        }
    }
}

Subtask #1
5.55555555556 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 503 ms 88356 KB Output isn't correct
2 Execution timed out 1100 ms 88304 KB Time limit exceeded
3 Execution timed out 1088 ms 88276 KB Time limit exceeded
4 Correct 553 ms 88360 KB Output is correct
5 Correct 681 ms 88352 KB Output is correct
6 Incorrect 461 ms 88392 KB Output isn't correct
7 Execution timed out 1103 ms 88268 KB Time limit exceeded
8 Execution timed out 1085 ms 88240 KB Time limit exceeded
9 Execution timed out 1098 ms 88268 KB Time limit exceeded
10 Execution timed out 1089 ms 88356 KB Time limit exceeded
11 Execution timed out 1102 ms 88276 KB Time limit exceeded
12 Correct 509 ms 88268 KB Output is correct
13 Execution timed out 1084 ms 88404 KB Time limit exceeded
14 Execution timed out 1096 ms 88392 KB Time limit exceeded
15 Execution timed out 1100 ms 88324 KB Time limit exceeded
16 Execution timed out 1101 ms 88276 KB Time limit exceeded
17 Correct 867 ms 88360 KB Output is correct
18 Correct 535 ms 88276 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1091 ms 89036 KB Time limit exceeded
2 Execution timed out 1094 ms 93644 KB Time limit exceeded
3 Execution timed out 1100 ms 92420 KB Time limit exceeded
4 Execution timed out 1057 ms 88536 KB Time limit exceeded
5 Execution timed out 1086 ms 91340 KB Time limit exceeded
6 Execution timed out 1051 ms 88396 KB Time limit exceeded
7 Execution timed out 1091 ms 88980 KB Time limit exceeded
8 Execution timed out 1096 ms 88416 KB Time limit exceeded
9 Execution timed out 1093 ms 92536 KB Time limit exceeded
10 Execution timed out 1104 ms 92364 KB Time limit exceeded
11 Execution timed out 1103 ms 90600 KB Time limit exceeded
12 Execution timed out 1102 ms 88392 KB Time limit exceeded
13 Execution timed out 1031 ms 88532 KB Time limit exceeded
14 Execution timed out 1098 ms 88492 KB Time limit exceeded
15 Execution timed out 1098 ms 90700 KB Time limit exceeded
16 Execution timed out 1063 ms 93644 KB Time limit exceeded
17 Execution timed out 1103 ms 88512 KB Time limit exceeded
18 Execution timed out 1091 ms 94116 KB Time limit exceeded

Subtask #3
1.42857142857 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1094 ms 91220 KB Time limit exceeded
2 Execution timed out 1081 ms 91412 KB Time limit exceeded
3 Execution timed out 1099 ms 91252 KB Time limit exceeded
4 Execution timed out 1098 ms 88524 KB Time limit exceeded
5 Execution timed out 1095 ms 94160 KB Time limit exceeded
6 Execution timed out 1102 ms 88764 KB Time limit exceeded
7 Execution timed out 1104 ms 94156 KB Time limit exceeded
8 Execution timed out 1096 ms 91204 KB Time limit exceeded
9 Execution timed out 1098 ms 91292 KB Time limit exceeded
10 Execution timed out 1098 ms 88660 KB Time limit exceeded
11 Execution timed out 1085 ms 88520 KB Time limit exceeded
12 Execution timed out 1101 ms 88708 KB Time limit exceeded
13 Execution timed out 1090 ms 90008 KB Time limit exceeded
14 Execution timed out 1095 ms 88244 KB Time limit exceeded
15 Execution timed out 1094 ms 88656 KB Time limit exceeded
16 Execution timed out 1093 ms 88656 KB Time limit exceeded
17 Execution timed out 1090 ms 90972 KB Time limit exceeded
18 Execution timed out 1104 ms 91372 KB Time limit exceeded
19 Execution timed out 1096 ms 88652 KB Time limit exceeded
20 Execution timed out 1077 ms 91312 KB Time limit exceeded
21 Execution timed out 1060 ms 88408 KB Time limit exceeded
22 Execution timed out 1081 ms 94376 KB Time limit exceeded
23 Execution timed out 1092 ms 90160 KB Time limit exceeded
24 Execution timed out 1100 ms 88728 KB Time limit exceeded
25 Execution timed out 1100 ms 88652 KB Time limit exceeded
26 Execution timed out 1096 ms 88548 KB Time limit exceeded
27 Execution timed out 1093 ms 94284 KB Time limit exceeded
28 Execution timed out 1093 ms 88404 KB Time limit exceeded
29 Execution timed out 1094 ms 94160 KB Time limit exceeded
30 Execution timed out 1050 ms 92364 KB Time limit exceeded
31 Execution timed out 1096 ms 88656 KB Time limit exceeded
32 Execution timed out 1103 ms 88532 KB Time limit exceeded
33 Correct 770 ms 89328 KB Output is correct
34 Execution timed out 1102 ms 94180 KB Time limit exceeded
35 Execution timed out 1087 ms 88372 KB Time limit exceeded
36 Execution timed out 1052 ms 93648 KB Time limit exceeded
37 Execution timed out 1093 ms 94144 KB Time limit exceeded
38 Execution timed out 1076 ms 88944 KB Time limit exceeded
39 Execution timed out 1095 ms 88492 KB Time limit exceeded
40 Execution timed out 1087 ms 88824 KB Time limit exceeded
41 Execution timed out 1090 ms 94244 KB Time limit exceeded
42 Execution timed out 1095 ms 88508 KB Time limit exceeded