oj.uz

Submission #318120

# Submission time Handle Problem Language Result Execution time Memory
318120 2020-10-31T13:18:19 Z shivensinha4 Brunhilda’s Birthday (BOI13_brunhilda) C++17
100 / 100
 721 ms 158692 KB 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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;
}

Compilation message

brunhilda.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
brunhilda.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 78820 KB Output is correct
2 Correct 283 ms 156900 KB Output is correct
3 Correct 227 ms 79788 KB Output is correct
4 Correct 228 ms 156924 KB Output is correct
5 Correct 262 ms 156900 KB Output is correct
6 Correct 206 ms 78824 KB Output is correct
7 Correct 225 ms 79844 KB Output is correct
8 Correct 238 ms 82404 KB Output is correct
9 Correct 297 ms 156884 KB Output is correct
10 Correct 334 ms 156900 KB Output is correct
11 Correct 327 ms 156892 KB Output is correct
12 Correct 225 ms 156900 KB Output is correct
13 Correct 542 ms 156896 KB Output is correct
14 Correct 538 ms 157028 KB Output is correct
15 Correct 295 ms 156904 KB Output is correct
16 Correct 282 ms 156900 KB Output is correct
17 Correct 280 ms 157028 KB Output is correct
18 Correct 228 ms 157156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 157028 KB Output is correct
2 Correct 287 ms 157668 KB Output is correct
3 Correct 662 ms 157372 KB Output is correct
4 Correct 303 ms 156900 KB Output is correct
5 Correct 473 ms 157284 KB Output is correct
6 Correct 286 ms 156900 KB Output is correct
7 Correct 265 ms 157024 KB Output is correct
8 Correct 310 ms 156900 KB Output is correct
9 Correct 558 ms 157416 KB Output is correct
10 Correct 658 ms 157412 KB Output is correct
11 Correct 645 ms 157164 KB Output is correct
12 Correct 383 ms 156900 KB Output is correct
13 Correct 243 ms 156900 KB Output is correct
14 Correct 311 ms 156896 KB Output is correct
15 Correct 543 ms 157284 KB Output is correct
16 Correct 287 ms 157668 KB Output is correct
17 Correct 551 ms 157028 KB Output is correct
18 Correct 555 ms 157668 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 157668 KB Output is correct
2 Correct 677 ms 157668 KB Output is correct
3 Correct 672 ms 157924 KB Output is correct
4 Correct 419 ms 157864 KB Output is correct
5 Correct 330 ms 158656 KB Output is correct
6 Correct 564 ms 157888 KB Output is correct
7 Correct 488 ms 158180 KB Output is correct
8 Correct 562 ms 157664 KB Output is correct
9 Correct 558 ms 157568 KB Output is correct
10 Correct 447 ms 157032 KB Output is correct
11 Correct 396 ms 157180 KB Output is correct
12 Correct 508 ms 157156 KB Output is correct
13 Correct 637 ms 158168 KB Output is correct
14 Correct 373 ms 158308 KB Output is correct
15 Correct 525 ms 157284 KB Output is correct
16 Correct 591 ms 157196 KB Output is correct
17 Correct 524 ms 157428 KB Output is correct
18 Correct 672 ms 157540 KB Output is correct
19 Correct 257 ms 157156 KB Output is correct
20 Correct 664 ms 157796 KB Output is correct
21 Correct 441 ms 158360 KB Output is correct
22 Correct 690 ms 158564 KB Output is correct
23 Correct 340 ms 158120 KB Output is correct
24 Correct 282 ms 157924 KB Output is correct
25 Correct 452 ms 157924 KB Output is correct
26 Correct 409 ms 157796 KB Output is correct
27 Correct 721 ms 158180 KB Output is correct
28 Correct 283 ms 158052 KB Output is correct
29 Correct 645 ms 158564 KB Output is correct
30 Correct 599 ms 158436 KB Output is correct
31 Correct 319 ms 157928 KB Output is correct
32 Correct 370 ms 157924 KB Output is correct
33 Correct 280 ms 157796 KB Output is correct
34 Correct 505 ms 158176 KB Output is correct
35 Correct 307 ms 158052 KB Output is correct
36 Correct 661 ms 158560 KB Output is correct
37 Correct 346 ms 158692 KB Output is correct
38 Correct 547 ms 158052 KB Output is correct
39 Correct 299 ms 158052 KB Output is correct
40 Correct 471 ms 158052 KB Output is correct
41 Correct 441 ms 158148 KB Output is correct
42 Correct 613 ms 158052 KB Output is correct