oj.uz

Submission #60814

# Submission time Handle Problem Language Result Execution time Memory
60814 2018-07-24T17:28:47 Z RezwanArefin01 Brunhilda’s Birthday (BOI13_brunhilda) C++17
97.7778 / 100
 603 ms 79548 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int N = 1e7 + 1; 
const int M = 1e5 + 1; 
int m, q, d[N], p, dp[N]; 

int main(int argc, char const *argv[]) {
	memset(dp, 127, sizeof dp); 
	scanf("%d %d", &m, &q); 
	for(int i = 0; i < m; i++) { 
		scanf("%d", &p); 
		for(int j = 0; j < N; j += p) d[j] = p; 
	}	
	int prv = 0; dp[0] = 0; 
	for(int i = 1; i < N; i++) {
		while(prv < i) {
			if(!d[prv] || prv + d[prv] <= i) ++prv; 
			else break; 
		}
		if(prv == i) break; 
		dp[i] = dp[prv] + 1; 
	}
	while(q--) {
		int x; scanf("%d", &x);
		if(dp[x] >= x) puts("oo"); 
		else printf("%d\n", dp[x]);
	}
}

Compilation message

brunhilda.cpp: In function 'int main(int, const char**)':
brunhilda.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &m, &q); 
  ~~~~~^~~~~~~~~~~~~~~~~
brunhilda.cpp:15:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &p); 
   ~~~~~^~~~~~~~~~
brunhilda.cpp:28:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x; scanf("%d", &x);
          ~~~~~^~~~~~~~~~

Subtask #1
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 78548 KB Output is correct
2 Correct 155 ms 78744 KB Output is correct
3 Correct 91 ms 78744 KB Output is correct
4 Correct 114 ms 78808 KB Output is correct
5 Correct 177 ms 78808 KB Output is correct
6 Correct 74 ms 78808 KB Output is correct
7 Correct 87 ms 78908 KB Output is correct
8 Correct 100 ms 78908 KB Output is correct
9 Correct 189 ms 78908 KB Output is correct
10 Correct 251 ms 78908 KB Output is correct
11 Correct 244 ms 78936 KB Output is correct
12 Correct 149 ms 78936 KB Output is correct
13 Correct 391 ms 78936 KB Output is correct
14 Incorrect 368 ms 78936 KB Output isn't correct
15 Correct 193 ms 78936 KB Output is correct
16 Correct 202 ms 78936 KB Output is correct
17 Incorrect 182 ms 78936 KB Output isn't correct
18 Correct 137 ms 78936 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 78936 KB Output is correct
2 Correct 187 ms 78936 KB Output is correct
3 Correct 462 ms 78972 KB Output is correct
4 Correct 208 ms 78972 KB Output is correct
5 Correct 365 ms 78972 KB Output is correct
6 Correct 153 ms 78972 KB Output is correct
7 Correct 175 ms 78972 KB Output is correct
8 Correct 225 ms 78972 KB Output is correct
9 Correct 388 ms 78972 KB Output is correct
10 Correct 509 ms 78972 KB Output is correct
11 Correct 424 ms 78972 KB Output is correct
12 Correct 316 ms 78972 KB Output is correct
13 Correct 138 ms 78972 KB Output is correct
14 Correct 240 ms 78972 KB Output is correct
15 Correct 394 ms 78988 KB Output is correct
16 Correct 197 ms 78988 KB Output is correct
17 Correct 487 ms 78988 KB Output is correct
18 Correct 431 ms 78992 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 78992 KB Output is correct
2 Correct 511 ms 79004 KB Output is correct
3 Correct 480 ms 79148 KB Output is correct
4 Correct 312 ms 79148 KB Output is correct
5 Correct 294 ms 79148 KB Output is correct
6 Correct 417 ms 79184 KB Output is correct
7 Correct 419 ms 79184 KB Output is correct
8 Correct 389 ms 79184 KB Output is correct
9 Correct 422 ms 79184 KB Output is correct
10 Correct 317 ms 79184 KB Output is correct
11 Correct 306 ms 79184 KB Output is correct
12 Correct 340 ms 79184 KB Output is correct
13 Correct 516 ms 79184 KB Output is correct
14 Correct 323 ms 79548 KB Output is correct
15 Correct 383 ms 79548 KB Output is correct
16 Correct 400 ms 79548 KB Output is correct
17 Correct 434 ms 79548 KB Output is correct
18 Correct 439 ms 79548 KB Output is correct
19 Correct 148 ms 79548 KB Output is correct
20 Correct 445 ms 79548 KB Output is correct
21 Correct 297 ms 79548 KB Output is correct
22 Correct 497 ms 79548 KB Output is correct
23 Correct 235 ms 79548 KB Output is correct
24 Correct 238 ms 79548 KB Output is correct
25 Correct 387 ms 79548 KB Output is correct
26 Correct 334 ms 79548 KB Output is correct
27 Correct 603 ms 79548 KB Output is correct
28 Correct 229 ms 79548 KB Output is correct
29 Correct 591 ms 79548 KB Output is correct
30 Correct 464 ms 79548 KB Output is correct
31 Correct 257 ms 79548 KB Output is correct
32 Correct 282 ms 79548 KB Output is correct
33 Correct 179 ms 79548 KB Output is correct
34 Correct 423 ms 79548 KB Output is correct
35 Correct 221 ms 79548 KB Output is correct
36 Correct 446 ms 79548 KB Output is correct
37 Correct 254 ms 79548 KB Output is correct
38 Correct 428 ms 79548 KB Output is correct
39 Correct 206 ms 79548 KB Output is correct
40 Correct 366 ms 79548 KB Output is correct
41 Correct 291 ms 79548 KB Output is correct
42 Correct 471 ms 79548 KB Output is correct