oj.uz

답안 #318122

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
318122 2020-10-31T13:18:58 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 660 ms 157540 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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 MXN = 2e7;
int jmp[MXN+2], ans[MXN+2];

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int m, q; cin >> m >> q;
	for_(i, 0, m) {
		int k; cin >> k;
		for (int j = k; j <= MXN; j += k) {
			jmp[j-1] = max(jmp[j-1], k-1);
		}
	}
	
	for (int i = MXN; i >= 1; i--) jmp[i] = max(jmp[i], jmp[i+1]-1);
	
	for_(i, 1, MXN+1) if (jmp[i] and (ans[i-jmp[i]] or i == jmp[i])) ans[i] = ans[i-jmp[i]]+1;
	
	for_(i, 0, q) {
		int k; cin >> k;
		if (ans[k]) cout << ans[k];
		else cout << "oo";
		cout << endl;
	}

	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 153 ms 78864 KB Output is correct
2 Correct 229 ms 156900 KB Output is correct
3 Correct 171 ms 79844 KB Output is correct
4 Correct 174 ms 157028 KB Output is correct
5 Correct 199 ms 156900 KB Output is correct
6 Correct 149 ms 78820 KB Output is correct
7 Correct 169 ms 79848 KB Output is correct
8 Correct 177 ms 82404 KB Output is correct
9 Correct 240 ms 156888 KB Output is correct
10 Correct 278 ms 156900 KB Output is correct
11 Correct 261 ms 156900 KB Output is correct
12 Correct 171 ms 156900 KB Output is correct
13 Correct 466 ms 156900 KB Output is correct
14 Correct 467 ms 156884 KB Output is correct
15 Correct 238 ms 156920 KB Output is correct
16 Correct 221 ms 156900 KB Output is correct
17 Correct 220 ms 156880 KB Output is correct
18 Correct 183 ms 156900 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 206 ms 156900 KB Output is correct
2 Correct 230 ms 156900 KB Output is correct
3 Correct 585 ms 156880 KB Output is correct
4 Correct 261 ms 156888 KB Output is correct
5 Correct 413 ms 156848 KB Output is correct
6 Correct 215 ms 156900 KB Output is correct
7 Correct 207 ms 157028 KB Output is correct
8 Correct 246 ms 156900 KB Output is correct
9 Correct 476 ms 157024 KB Output is correct
10 Correct 582 ms 156904 KB Output is correct
11 Correct 569 ms 156900 KB Output is correct
12 Correct 322 ms 156900 KB Output is correct
13 Correct 186 ms 156992 KB Output is correct
14 Correct 254 ms 156900 KB Output is correct
15 Correct 472 ms 156900 KB Output is correct
16 Correct 232 ms 156900 KB Output is correct
17 Correct 487 ms 156900 KB Output is correct
18 Correct 470 ms 156900 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 478 ms 157028 KB Output is correct
2 Correct 596 ms 156900 KB Output is correct
3 Correct 594 ms 157028 KB Output is correct
4 Correct 351 ms 157156 KB Output is correct
5 Correct 269 ms 157252 KB Output is correct
6 Correct 477 ms 157284 KB Output is correct
7 Correct 434 ms 157028 KB Output is correct
8 Correct 485 ms 157156 KB Output is correct
9 Correct 478 ms 157028 KB Output is correct
10 Correct 389 ms 156884 KB Output is correct
11 Correct 329 ms 156900 KB Output is correct
12 Correct 444 ms 157012 KB Output is correct
13 Correct 563 ms 157148 KB Output is correct
14 Correct 319 ms 157540 KB Output is correct
15 Correct 466 ms 157028 KB Output is correct
16 Correct 515 ms 157156 KB Output is correct
17 Correct 473 ms 156888 KB Output is correct
18 Correct 593 ms 157028 KB Output is correct
19 Correct 205 ms 156900 KB Output is correct
20 Correct 592 ms 157028 KB Output is correct
21 Correct 369 ms 157536 KB Output is correct
22 Correct 600 ms 157160 KB Output is correct
23 Correct 275 ms 157156 KB Output is correct
24 Correct 225 ms 157284 KB Output is correct
25 Correct 398 ms 157284 KB Output is correct
26 Correct 354 ms 157156 KB Output is correct
27 Correct 660 ms 157028 KB Output is correct
28 Correct 233 ms 157284 KB Output is correct
29 Correct 576 ms 157284 KB Output is correct
30 Correct 532 ms 157284 KB Output is correct
31 Correct 276 ms 157156 KB Output is correct
32 Correct 298 ms 157284 KB Output is correct
33 Correct 197 ms 157156 KB Output is correct
34 Correct 433 ms 157008 KB Output is correct
35 Correct 240 ms 157156 KB Output is correct
36 Correct 581 ms 157156 KB Output is correct
37 Correct 270 ms 157160 KB Output is correct
38 Correct 479 ms 157156 KB Output is correct
39 Correct 243 ms 157156 KB Output is correct
40 Correct 418 ms 157140 KB Output is correct
41 Correct 372 ms 157028 KB Output is correct
42 Correct 526 ms 157272 KB Output is correct