oj.uz

Submission #318121

# Submission time Handle Problem Language Result Execution time Memory
318121 2020-10-31T13:18:45 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 651 ms 157932 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

# Verdict Execution time Memory Grader output
1 Correct 151 ms 78820 KB Output is correct
2 Correct 224 ms 156900 KB Output is correct
3 Correct 172 ms 79864 KB Output is correct
4 Correct 176 ms 156900 KB Output is correct
5 Correct 201 ms 156904 KB Output is correct
6 Correct 149 ms 78820 KB Output is correct
7 Correct 172 ms 79848 KB Output is correct
8 Correct 186 ms 82404 KB Output is correct
9 Correct 238 ms 156900 KB Output is correct
10 Correct 283 ms 156900 KB Output is correct
11 Correct 273 ms 156900 KB Output is correct
12 Correct 173 ms 157028 KB Output is correct
13 Correct 470 ms 157028 KB Output is correct
14 Correct 475 ms 156988 KB Output is correct
15 Correct 240 ms 156900 KB Output is correct
16 Correct 227 ms 156900 KB Output is correct
17 Correct 223 ms 156956 KB Output is correct
18 Correct 174 ms 156900 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 157028 KB Output is correct
2 Correct 232 ms 157412 KB Output is correct
3 Correct 582 ms 157360 KB Output is correct
4 Correct 258 ms 156900 KB Output is correct
5 Correct 413 ms 157284 KB Output is correct
6 Correct 219 ms 156900 KB Output is correct
7 Correct 211 ms 157156 KB Output is correct
8 Correct 254 ms 156900 KB Output is correct
9 Correct 489 ms 157536 KB Output is correct
10 Correct 586 ms 157412 KB Output is correct
11 Correct 572 ms 157156 KB Output is correct
12 Correct 323 ms 156900 KB Output is correct
13 Correct 189 ms 156908 KB Output is correct
14 Correct 254 ms 156900 KB Output is correct
15 Correct 475 ms 157184 KB Output is correct
16 Correct 232 ms 157412 KB Output is correct
17 Correct 493 ms 156900 KB Output is correct
18 Correct 470 ms 157412 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 485 ms 157544 KB Output is correct
2 Correct 598 ms 157412 KB Output is correct
3 Correct 610 ms 157540 KB Output is correct
4 Correct 357 ms 157668 KB Output is correct
5 Correct 271 ms 157668 KB Output is correct
6 Correct 481 ms 157796 KB Output is correct
7 Correct 429 ms 157540 KB Output is correct
8 Correct 484 ms 157668 KB Output is correct
9 Correct 481 ms 157540 KB Output is correct
10 Correct 399 ms 157028 KB Output is correct
11 Correct 330 ms 157288 KB Output is correct
12 Correct 456 ms 157156 KB Output is correct
13 Correct 562 ms 157932 KB Output is correct
14 Correct 320 ms 157924 KB Output is correct
15 Correct 469 ms 157156 KB Output is correct
16 Correct 520 ms 157156 KB Output is correct
17 Correct 470 ms 157412 KB Output is correct
18 Correct 603 ms 157668 KB Output is correct
19 Correct 208 ms 157156 KB Output is correct
20 Correct 614 ms 157544 KB Output is correct
21 Correct 375 ms 157924 KB Output is correct
22 Correct 614 ms 157412 KB Output is correct
23 Correct 278 ms 157540 KB Output is correct
24 Correct 224 ms 157540 KB Output is correct
25 Correct 399 ms 157668 KB Output is correct
26 Correct 356 ms 157540 KB Output is correct
27 Correct 651 ms 157412 KB Output is correct
28 Correct 226 ms 157668 KB Output is correct
29 Correct 580 ms 157540 KB Output is correct
30 Correct 529 ms 157540 KB Output is correct
31 Correct 264 ms 157652 KB Output is correct
32 Correct 294 ms 157540 KB Output is correct
33 Correct 202 ms 157540 KB Output is correct
34 Correct 433 ms 157392 KB Output is correct
35 Correct 242 ms 157544 KB Output is correct
36 Correct 585 ms 157412 KB Output is correct
37 Correct 275 ms 157444 KB Output is correct
38 Correct 485 ms 157540 KB Output is correct
39 Correct 245 ms 157796 KB Output is correct
40 Correct 417 ms 157668 KB Output is correct
41 Correct 378 ms 157540 KB Output is correct
42 Correct 545 ms 157796 KB Output is correct