oj.uz

답안 #313956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
313956 2020-10-17T15:15:46 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 136 ms 24440 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);
	
	multiset<int> vals;
	for (int i: primes) vals.insert(0);
	
	for_(i, 1, MXV+1) {
		for (auto p: facs[i]) vals.erase(vals.find(curVal[p]));
		if (vals.size()) ans[i] = *vals.begin()+1;
		else ans[i] = -1;
		for (auto p: facs[i]) vals.insert(curVal[p] = ans[i]);
	}
	
	for_(x, 0, q) {
		int k; cin >> k;
		if (ans[k] == -1) cout << "oo";
		else cout << ans[k];
		cout << endl;
	}

	return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:29:11: warning: unused variable 'i' [-Wunused-variable]
   29 |  for (int i: primes) vals.insert(0);
      |           ^

Subtask #1
17.7777777778 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 3584 KB Output isn't correct
2 Correct 22 ms 5376 KB Output is correct
3 Correct 13 ms 4992 KB Output is correct
4 Correct 6 ms 3456 KB Output is correct
5 Correct 11 ms 3968 KB Output is correct
6 Incorrect 5 ms 3584 KB Output isn't correct
7 Correct 13 ms 4992 KB Output is correct
8 Correct 17 ms 5376 KB Output is correct
9 Correct 24 ms 5624 KB Output is correct
10 Correct 28 ms 5760 KB Output is correct
11 Correct 22 ms 5240 KB Output is correct
12 Correct 4 ms 3200 KB Output is correct
13 Correct 57 ms 6008 KB Output is correct
14 Correct 59 ms 6136 KB Output is correct
15 Correct 21 ms 5248 KB Output is correct
16 Correct 22 ms 5376 KB Output is correct
17 Correct 12 ms 3968 KB Output is correct
18 Correct 6 ms 3456 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 8960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Incorrect 40 ms 9336 KB Output isn't correct
3 Runtime error 115 ms 21088 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 25 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 72 ms 17656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 25 ms 10624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 16 ms 8960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 19 ms 8832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 97 ms 20472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 124 ms 20920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 105 ms 17656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 39 ms 11640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 15 ms 8704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 22 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 91 ms 17532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 48 ms 18040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 67 ms 12536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 113 ms 23544 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 98 ms 18600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 110 ms 19064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 105 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 44 ms 12408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 49 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 68 ms 13884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 80 ms 22368 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 104 ms 18552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 101 ms 18556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 56 ms 12664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 32 ms 11512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 61 ms 13436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 85 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 51 ms 6776 KB Output isn't correct
15 Runtime error 73 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 80 ms 13816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 73 ms 17404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 112 ms 19068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 22 ms 10112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 105 ms 18808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 48 ms 11768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 128 ms 24312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 26 ms 11520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 13 ms 8064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 46 ms 12032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 46 ms 12408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 136 ms 24440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 18 ms 9216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 95 ms 23904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 70 ms 20216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 21 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 25 ms 10360 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 Incorrect 78 ms 12024 KB Output isn't correct
35 Runtime error 20 ms 9472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 123 ms 23212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Incorrect 66 ms 10744 KB Output isn't correct
38 Runtime error 64 ms 13816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 16 ms 8628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 55 ms 13560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 88 ms 22904 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 72 ms 12668 KB Execution killed with signal 11 (could be triggered by violating memory limits)