oj.uz

Submission #36501

# Submission time Handle Problem Language Result Execution time Memory
36501 2017-12-10T03:19:45 Z cheater2k Brunhilda’s Birthday (BOI13_brunhilda) C++14
60 / 100
 683 ms 80140 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 10000000;
const int inf = 1e9 + 10;

int nprime, nquery;
int maxdiv[MAX + 5];
int dp[MAX + 5];

int main() {
	scanf("%d %d", &nprime, &nquery);
	for (int i = 1; i <= MAX; ++i) dp[i] = inf;
	for (int i = 1; i <= nprime; ++i) {
		int p; scanf("%d", &p);
		for (int j = 0; j <= MAX; j += p) maxdiv[j] = p;
	}
	
	int cur = 0;
	for (int i = 1; i <= MAX; ++i) {
		while(cur < i) {
			if (!maxdiv[cur] || cur + maxdiv[cur] <= i) ++cur;
			else break;
		}
		if (cur == i) continue;
		dp[i] = min(dp[i], dp[cur] + 1);
	}

	while(nquery--) {
		int n; cin >> n;
		if (dp[n] != inf) printf("%d\n", dp[n]);
		else printf("oo\n");
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:12:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &nprime, &nquery);
                                  ^
brunhilda.cpp:15:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p);
                         ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 80140 KB Output is correct
2 Correct 109 ms 80140 KB Output is correct
3 Correct 103 ms 80140 KB Output is correct
4 Correct 129 ms 80140 KB Output is correct
5 Correct 133 ms 80140 KB Output is correct
6 Correct 113 ms 80140 KB Output is correct
7 Correct 96 ms 80140 KB Output is correct
8 Correct 116 ms 80140 KB Output is correct
9 Correct 163 ms 80140 KB Output is correct
10 Correct 169 ms 80140 KB Output is correct
11 Correct 176 ms 80140 KB Output is correct
12 Correct 69 ms 80140 KB Output is correct
13 Correct 316 ms 80140 KB Output is correct
14 Correct 376 ms 80140 KB Output is correct
15 Correct 136 ms 80140 KB Output is correct
16 Correct 126 ms 80140 KB Output is correct
17 Correct 166 ms 80140 KB Output is correct
18 Correct 136 ms 80140 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 80140 KB Output is correct
2 Correct 146 ms 80140 KB Output is correct
3 Correct 456 ms 80140 KB Output is correct
4 Correct 196 ms 80140 KB Output is correct
5 Correct 289 ms 80140 KB Output is correct
6 Correct 116 ms 80140 KB Output is correct
7 Correct 123 ms 80140 KB Output is correct
8 Correct 163 ms 80140 KB Output is correct
9 Correct 346 ms 80140 KB Output is correct
10 Correct 456 ms 80140 KB Output is correct
11 Correct 436 ms 80140 KB Output is correct
12 Correct 223 ms 80140 KB Output is correct
13 Correct 93 ms 80140 KB Output is correct
14 Correct 199 ms 80140 KB Output is correct
15 Correct 363 ms 80140 KB Output is correct
16 Correct 123 ms 80140 KB Output is correct
17 Correct 369 ms 80140 KB Output is correct
18 Correct 379 ms 80140 KB Output is correct

Subtask #3
20.0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 599 ms 80140 KB Execution timed out (wall clock limit exceeded)
2 Correct 549 ms 80140 KB Output is correct
3 Runtime error 683 ms 80140 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 479 ms 80140 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 363 ms 80140 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 569 ms 80140 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 523 ms 80140 KB Execution timed out (wall clock limit exceeded)
8 Correct 563 ms 80140 KB Output is correct
9 Correct 489 ms 80140 KB Output is correct
10 Correct 306 ms 80140 KB Output is correct
11 Correct 366 ms 80140 KB Output is correct
12 Correct 383 ms 80140 KB Output is correct
13 Runtime error 596 ms 80140 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 399 ms 80140 KB Execution timed out (wall clock limit exceeded)
15 Correct 513 ms 80140 KB Output is correct
16 Correct 546 ms 80140 KB Output is correct
17 Correct 369 ms 80140 KB Output is correct
18 Correct 499 ms 80140 KB Output is correct
19 Correct 183 ms 80140 KB Output is correct
20 Correct 673 ms 80140 KB Output is correct
21 Runtime error 429 ms 80140 KB Execution timed out (wall clock limit exceeded)
22 Runtime error 683 ms 80140 KB Execution timed out (wall clock limit exceeded)
23 Runtime error 383 ms 80140 KB Execution timed out (wall clock limit exceeded)
24 Runtime error 333 ms 80140 KB Execution timed out (wall clock limit exceeded)
25 Runtime error 509 ms 80140 KB Execution timed out (wall clock limit exceeded)
26 Runtime error 399 ms 80140 KB Execution timed out (wall clock limit exceeded)
27 Correct 646 ms 80140 KB Output is correct
28 Runtime error 316 ms 80140 KB Execution timed out (wall clock limit exceeded)
29 Runtime error 626 ms 80140 KB Execution timed out (wall clock limit exceeded)
30 Runtime error 613 ms 80140 KB Execution timed out (wall clock limit exceeded)
31 Runtime error 329 ms 80140 KB Execution timed out (wall clock limit exceeded)
32 Runtime error 399 ms 80140 KB Execution timed out (wall clock limit exceeded)
33 Correct 279 ms 80140 KB Output is correct
34 Runtime error 516 ms 80140 KB Execution timed out (wall clock limit exceeded)
35 Runtime error 323 ms 80140 KB Execution timed out (wall clock limit exceeded)
36 Runtime error 653 ms 80140 KB Execution timed out (wall clock limit exceeded)
37 Runtime error 363 ms 80140 KB Execution timed out (wall clock limit exceeded)
38 Runtime error 526 ms 80140 KB Execution timed out (wall clock limit exceeded)
39 Runtime error 343 ms 80140 KB Execution timed out (wall clock limit exceeded)
40 Runtime error 496 ms 80140 KB Execution timed out (wall clock limit exceeded)
41 Runtime error 473 ms 80140 KB Execution timed out (wall clock limit exceeded)
42 Runtime error 553 ms 80140 KB Execution timed out (wall clock limit exceeded)