oj.uz

답안 #313960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313960 2020-10-17T15:27:00 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 194 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;
		assert(k <= MXV);
		if (ans[k] == -1) cout << "oo";
		else cout << ans[k];
		cout << endl;
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 3584 KB Output is correct
2 Correct 28 ms 5376 KB Output is correct
3 Correct 16 ms 4992 KB Output is correct
4 Correct 7 ms 3328 KB Output is correct
5 Correct 11 ms 3840 KB Output is correct
6 Correct 4 ms 3584 KB Output is correct
7 Correct 17 ms 4992 KB Output is correct
8 Correct 23 ms 5376 KB Output is correct
9 Correct 35 ms 5624 KB Output is correct
10 Correct 42 ms 5752 KB Output is correct
11 Correct 32 ms 5240 KB Output is correct
12 Correct 5 ms 3200 KB Output is correct
13 Correct 84 ms 6008 KB Output is correct
14 Correct 89 ms 6008 KB Output is correct
15 Correct 28 ms 5248 KB Output is correct
16 Correct 28 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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 21 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 Runtime error 167 ms 20348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 28 ms 9976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 93 ms 17272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 31 ms 10748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 19 ms 8960 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 19936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 168 ms 20336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 152 ms 17400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 50 ms 11768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 17 ms 8704 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 130 ms 17144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 54 ms 17400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 97 ms 12664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 135 ms 22776 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 137 ms 18236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 165 ms 18920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 159 ms 18296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 60 ms 12408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 52 ms 17912 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 92 ms 13700 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 100 ms 21496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 140 ms 18044 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 134 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 64 ms 12408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 46 ms 11384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 86 ms 13304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 127 ms 16120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 55 ms 11512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 97 ms 13312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 109 ms 13692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 99 ms 17016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 157 ms 18552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 27 ms 9980 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 164 ms 18552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 66 ms 11768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 177 ms 23416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 30 ms 11136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 15 ms 8192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 59 ms 11896 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 64 ms 12408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 194 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 125 ms 23048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 95 ms 19576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 26 ms 9720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 32 ms 10232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 12 ms 7680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 97 ms 21496 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 23 ms 9464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 175 ms 22440 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 13688 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 74 ms 13432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 107 ms 22264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 104 ms 12536 KB Execution killed with signal 11 (could be triggered by violating memory limits)