답안 #558900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558900	2022-05-08T23:45:33 Z	Olympia	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	15.3968 / 100	1000 ms	80520 KB

brunhilda

#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);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
        st.upd(i, 0);
    }
    sort(p.begin(), p.end()); 
    int mx = 10000000;
    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:37:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1

5.55555555556 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	345 ms	78488 KB	Output isn't correct
2	Execution timed out	1102 ms	78504 KB	Time limit exceeded
3	Execution timed out	1094 ms	78540 KB	Time limit exceeded
4	Correct	294 ms	78572 KB	Output is correct
5	Correct	512 ms	78568 KB	Output is correct
6	Incorrect	311 ms	78580 KB	Output isn't correct
7	Execution timed out	1094 ms	78480 KB	Time limit exceeded
8	Execution timed out	1104 ms	78568 KB	Time limit exceeded
9	Execution timed out	1089 ms	78504 KB	Time limit exceeded
10	Execution timed out	1101 ms	78540 KB	Time limit exceeded
11	Execution timed out	1100 ms	78544 KB	Time limit exceeded
12	Correct	270 ms	78584 KB	Output is correct
13	Execution timed out	1103 ms	78480 KB	Time limit exceeded
14	Execution timed out	1099 ms	78540 KB	Time limit exceeded
15	Execution timed out	1097 ms	78548 KB	Time limit exceeded
16	Execution timed out	1102 ms	78492 KB	Time limit exceeded
17	Correct	639 ms	78572 KB	Output is correct
18	Correct	286 ms	78576 KB	Output is correct

Subtask #2

5.55555555556 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	715 ms	78800 KB	Output is correct
2	Correct	888 ms	79660 KB	Output is correct
3	Execution timed out	1097 ms	79380 KB	Time limit exceeded
4	Execution timed out	1097 ms	78540 KB	Time limit exceeded
5	Execution timed out	1051 ms	79164 KB	Time limit exceeded
6	Execution timed out	1101 ms	78572 KB	Time limit exceeded
7	Correct	683 ms	78720 KB	Output is correct
8	Execution timed out	1086 ms	78536 KB	Time limit exceeded
9	Execution timed out	1097 ms	79428 KB	Time limit exceeded
10	Execution timed out	1099 ms	79404 KB	Time limit exceeded
11	Execution timed out	1100 ms	79072 KB	Time limit exceeded
12	Execution timed out	1090 ms	78548 KB	Time limit exceeded
13	Correct	709 ms	78612 KB	Output is correct
14	Execution timed out	1100 ms	78488 KB	Time limit exceeded
15	Execution timed out	1094 ms	78972 KB	Time limit exceeded
16	Correct	881 ms	79664 KB	Output is correct
17	Execution timed out	1087 ms	78496 KB	Time limit exceeded
18	Execution timed out	1099 ms	79736 KB	Time limit exceeded

Subtask #3

4.28571428571 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1088 ms	79120 KB	Time limit exceeded
2	Execution timed out	1090 ms	79160 KB	Time limit exceeded
3	Execution timed out	1097 ms	79160 KB	Time limit exceeded
4	Execution timed out	1094 ms	78608 KB	Time limit exceeded
5	Execution timed out	1056 ms	80520 KB	Time limit exceeded
6	Execution timed out	1095 ms	78636 KB	Time limit exceeded
7	Execution timed out	1062 ms	79748 KB	Time limit exceeded
8	Execution timed out	1089 ms	79052 KB	Time limit exceeded
9	Execution timed out	1098 ms	79112 KB	Time limit exceeded
10	Execution timed out	1096 ms	78604 KB	Time limit exceeded
11	Execution timed out	1089 ms	78528 KB	Time limit exceeded
12	Execution timed out	1080 ms	78588 KB	Time limit exceeded
13	Execution timed out	1092 ms	78868 KB	Time limit exceeded
14	Execution timed out	1095 ms	78548 KB	Time limit exceeded
15	Execution timed out	1060 ms	78540 KB	Time limit exceeded
16	Execution timed out	1093 ms	78548 KB	Time limit exceeded
17	Execution timed out	1097 ms	79060 KB	Time limit exceeded
18	Execution timed out	1093 ms	79180 KB	Time limit exceeded
19	Execution timed out	1041 ms	78632 KB	Time limit exceeded
20	Execution timed out	1100 ms	79180 KB	Time limit exceeded
21	Execution timed out	1101 ms	78548 KB	Time limit exceeded
22	Execution timed out	1097 ms	79648 KB	Time limit exceeded
23	Execution timed out	1080 ms	79580 KB	Time limit exceeded
24	Correct	616 ms	78844 KB	Output is correct
25	Execution timed out	1091 ms	78564 KB	Time limit exceeded
26	Execution timed out	1102 ms	78548 KB	Time limit exceeded
27	Execution timed out	1098 ms	79752 KB	Time limit exceeded
28	Incorrect	889 ms	78836 KB	Output isn't correct
29	Execution timed out	1101 ms	79692 KB	Time limit exceeded
30	Execution timed out	1078 ms	79308 KB	Time limit exceeded
31	Execution timed out	1077 ms	78536 KB	Time limit exceeded
32	Execution timed out	1102 ms	78548 KB	Time limit exceeded
33	Correct	446 ms	78840 KB	Output is correct
34	Execution timed out	1100 ms	79740 KB	Time limit exceeded
35	Execution timed out	1052 ms	78924 KB	Time limit exceeded
36	Execution timed out	1101 ms	79572 KB	Time limit exceeded
37	Execution timed out	1033 ms	79876 KB	Time limit exceeded
38	Execution timed out	1093 ms	78540 KB	Time limit exceeded
39	Correct	784 ms	78868 KB	Output is correct
40	Execution timed out	1100 ms	78640 KB	Time limit exceeded
41	Execution timed out	1081 ms	79820 KB	Time limit exceeded
42	Execution timed out	1102 ms	78480 KB	Time limit exceeded