oj.uz

Submission #313959

# Submission time Handle Problem Language Result Execution time Memory
313959 2020-10-17T15:26:24 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 198 ms 23544 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXV = 1e5;
vi facs[MXV+2];
int ans[MXV+2], curVal[MXV+2];


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, q; cin >> n >> q;
	vi primes(n);
	for_(i, 0, n) cin >> primes[i];
	for (int i: primes) for (int j = i; j <= MXV; j += i) facs[j].push_back(i);
	
	set<ii> vals;
	for (int i: primes) vals.insert({0, i});
	
	for_(i, 1, MXV+1) {
		//cout << i << ":: ";
		for (auto p: facs[i]) if (vals.count({curVal[p], p})) vals.erase({curVal[p], p});
		
		//for (ii c: vals) cout << c.first << " " << c.second << endl;
		//cout << endl;
		
		if (vals.size()) ans[i] = (*vals.begin()).first+1;
		else ans[i] = -1;
		
		if (ans[i] != -1) for (auto p: facs[i]) vals.insert({curVal[p] = ans[i], p});
		//cout << i << ": " << ans[i] << endl;
	}
	
	for_(x, 0, q) {
		int k; cin >> k;
		if (ans[k] == -1) cout << "oo";
		else cout << ans[k];
		cout << endl;
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3584 KB Output is correct
2 Correct 29 ms 5368 KB Output is correct
3 Correct 17 ms 4992 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 10 ms 3840 KB Output is correct
6 Correct 4 ms 3584 KB Output is correct
7 Correct 16 ms 4992 KB Output is correct
8 Correct 23 ms 5376 KB Output is correct
9 Correct 33 ms 5632 KB Output is correct
10 Correct 46 ms 5752 KB Output is correct
11 Correct 33 ms 5240 KB Output is correct
12 Correct 5 ms 3200 KB Output is correct
13 Correct 88 ms 6096 KB Output is correct
14 Correct 90 ms 6008 KB Output is correct
15 Correct 30 ms 5240 KB Output is correct
16 Correct 29 ms 5368 KB Output is correct
17 Correct 15 ms 3968 KB Output is correct
18 Correct 7 ms 3328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 8960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 54 ms 17400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 166 ms 10104 KB Output isn't correct
4 Runtime error 28 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 97 ms 17272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 29 ms 10620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 19 ms 8952 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 25 ms 8824 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 118 ms 19836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Incorrect 163 ms 10360 KB Output isn't correct
11 Runtime error 151 ms 17400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 53 ms 11640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 17 ms 8576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 28 ms 9848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 131 ms 17144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 53 ms 17400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 101 ms 12536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 137 ms 22776 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 148 ms 18296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 164 ms 18652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 166 ms 18424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 60 ms 12280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 53 ms 17912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 91 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 96 ms 21496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 147 ms 17988 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 140 ms 18168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 62 ms 12412 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 45 ms 11384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 87 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 131 ms 16244 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 56 ms 11512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 99 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 118 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 106 ms 17144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 163 ms 18680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 27 ms 10104 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 172 ms 9616 KB Output isn't correct
21 Runtime error 67 ms 11768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 186 ms 23416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 29 ms 11256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 15 ms 8064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 61 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 65 ms 12536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 198 ms 23544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 21 ms 9216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 129 ms 23188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 100 ms 19576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 27 ms 9720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 32 ms 10240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 12 ms 7552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 99 ms 21496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 24 ms 9432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 178 ms 22264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 52 ms 17912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 91 ms 13652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 19 ms 8576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 77 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 108 ms 22008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 110 ms 12496 KB Execution killed with signal 11 (could be triggered by violating memory limits)