oj.uz

Submission #558902

# Submission time Handle Problem Language Result Execution time Memory
558902 2022-05-08T23:50:37 Z Olympia Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 1000 ms 27392 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);
    for (int i = 0; i < M; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end()); 
    int mx = 1000000;
    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;
        }
    }
    int dp[M];
    multiset<int> ms;
    for (int i = 0; i < M; i++) {
        dp[i] = 0;
        ms.insert(dp[i]);
    }
    for (int i = 1; i < mx; i++) {
        int ans = 1e9;
        if (lpf[i] == -1) {
            ans = *ms.begin() + 1;
        } else {
            vector<int> invalid;
            int x = i;
            while (lpf[x] != -1) {
                invalid.push_back(lpf[x]);
                int a = p[lpf[x]];
                while (x % a == 0) x /= a;
            }
            for (int j: invalid) {
                assert(ms.count(dp[j]));
                ms.erase(ms.find(dp[j]));
            }
            if (!ms.empty()) {
                ans = *ms.begin() + 1;
            }
            for (int j: invalid) {
                ms.insert(dp[j]);
            }
            for (int j: invalid) {
                if (j >= 0 && j < (int)p.size()) {
                    ms.erase(ms.find(dp[j]));
                    dp[j] = ans;
                    ms.insert(dp[j]);
                }
            }
        }
        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:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int j = 0; j < p.size(); j++) {
      |                     ~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 8020 KB Output isn't correct
2 Correct 278 ms 8124 KB Output is correct
3 Correct 132 ms 8124 KB Output is correct
4 Correct 29 ms 8252 KB Output is correct
5 Correct 61 ms 8124 KB Output is correct
6 Incorrect 33 ms 8268 KB Output isn't correct
7 Correct 133 ms 8120 KB Output is correct
8 Correct 193 ms 8124 KB Output is correct
9 Correct 280 ms 8140 KB Output is correct
10 Correct 352 ms 8124 KB Output is correct
11 Correct 251 ms 8140 KB Output is correct
12 Correct 21 ms 8020 KB Output is correct
13 Correct 838 ms 8188 KB Output is correct
14 Correct 829 ms 8184 KB Output is correct
15 Correct 259 ms 8116 KB Output is correct
16 Correct 276 ms 8020 KB Output is correct
17 Correct 88 ms 8140 KB Output is correct
18 Correct 30 ms 8148 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 97 ms 17624 KB Execution killed with signal 11
2 Runtime error 187 ms 26456 KB Execution killed with signal 11
3 Execution timed out 1081 ms 11852 KB Time limit exceeded
4 Runtime error 193 ms 16624 KB Execution killed with signal 11
5 Runtime error 953 ms 21956 KB Execution killed with signal 11
6 Runtime error 273 ms 16376 KB Execution killed with signal 11
7 Runtime error 96 ms 17616 KB Execution killed with signal 11
8 Runtime error 184 ms 16376 KB Execution killed with signal 11
9 Execution timed out 1097 ms 11988 KB Time limit exceeded
10 Execution timed out 1062 ms 11852 KB Time limit exceeded
11 Execution timed out 1099 ms 10348 KB Time limit exceeded
12 Runtime error 466 ms 16464 KB Execution killed with signal 11
13 Runtime error 110 ms 16588 KB Execution killed with signal 11
14 Runtime error 194 ms 16616 KB Execution killed with signal 11
15 Execution timed out 1088 ms 10348 KB Time limit exceeded
16 Runtime error 183 ms 26412 KB Execution killed with signal 11
17 Runtime error 870 ms 16608 KB Execution killed with signal 11
18 Execution timed out 1092 ms 13516 KB Time limit exceeded

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 10816 KB Time limit exceeded
2 Execution timed out 1093 ms 10916 KB Time limit exceeded
3 Execution timed out 1083 ms 10832 KB Time limit exceeded
4 Runtime error 535 ms 16628 KB Execution killed with signal 11
5 Runtime error 177 ms 27244 KB Execution killed with signal 11
6 Runtime error 839 ms 17152 KB Execution killed with signal 11
7 Runtime error 737 ms 27392 KB Execution killed with signal 11
8 Execution timed out 1095 ms 10828 KB Time limit exceeded
9 Execution timed out 1070 ms 10836 KB Time limit exceeded
10 Runtime error 468 ms 16896 KB Execution killed with signal 11
11 Runtime error 336 ms 16688 KB Execution killed with signal 11
12 Runtime error 786 ms 16896 KB Execution killed with signal 11
13 Execution timed out 1088 ms 9684 KB Time limit exceeded
14 Runtime error 433 ms 16204 KB Execution killed with signal 11
15 Runtime error 947 ms 16872 KB Execution killed with signal 11
16 Execution timed out 1018 ms 17084 KB Time limit exceeded
17 Runtime error 989 ms 21264 KB Execution killed with signal 11
18 Execution timed out 1091 ms 10916 KB Time limit exceeded
19 Runtime error 194 ms 16844 KB Execution killed with signal 11
20 Execution timed out 1095 ms 10832 KB Time limit exceeded
21 Runtime error 566 ms 16196 KB Execution killed with signal 11
22 Execution timed out 1092 ms 13528 KB Time limit exceeded
23 Runtime error 183 ms 19532 KB Execution killed with signal 11
24 Runtime error 87 ms 16376 KB Execution killed with signal 11
25 Runtime error 569 ms 16604 KB Execution killed with signal 11
26 Runtime error 559 ms 16636 KB Execution killed with signal 11
27 Execution timed out 1090 ms 13520 KB Time limit exceeded
28 Runtime error 153 ms 16332 KB Execution killed with signal 11
29 Execution timed out 1076 ms 13532 KB Time limit exceeded
30 Runtime error 960 ms 24008 KB Execution killed with signal 11
31 Runtime error 191 ms 16684 KB Execution killed with signal 11
32 Runtime error 239 ms 16596 KB Execution killed with signal 11
33 Runtime error 53 ms 16396 KB Execution killed with signal 11
34 Runtime error 782 ms 27340 KB Execution killed with signal 11
35 Runtime error 161 ms 16436 KB Execution killed with signal 11
36 Execution timed out 1096 ms 13064 KB Time limit exceeded
37 Runtime error 177 ms 27280 KB Execution killed with signal 11
38 Runtime error 831 ms 17156 KB Execution killed with signal 11
39 Runtime error 106 ms 16452 KB Execution killed with signal 11
40 Runtime error 699 ms 17344 KB Execution killed with signal 11
41 Runtime error 947 ms 27332 KB Execution killed with signal 11
42 Runtime error 913 ms 16608 KB Execution killed with signal 11