oj.uz

Submission #134091

# Submission time Handle Problem Language Result Execution time Memory
134091 2019-07-22T04:17:40 Z wzy Brunhilda’s Birthday (BOI13_brunhilda) C++11
100 / 100
 460 ms 118776 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 100002;
#define pii pair<int,int> 
const int MX = 10000005;
int primes[N] ;
int m , q;
int dp[MX];
int adj[MX];
int vl[MX];
int dq[MX];
int currx = -1;
// valores formam sequencia (0 , 1 , 2, 3 ,...)
// pega o menor multiplo menor que i 
int32_t main(){
	scanf("%d%d" , &m , &q);
	for(int i = 0 ; i < MX ;i ++){
		dp[i] = 1000000000;
		adj[i] = -1;
		dq[i] = -1;
	}
	for(int i = 0 ; i < m ; i ++){
		scanf("%d" , &primes[i]);
		vl[++currx] = primes[i];
		adj[currx] = dq[0];
		dq[0] = currx;
	}
	dp[0] = 0;
	int curr = 0;	
	for(int i = 0 ; i < MX ; i ++){
		int w = dq[i];
		while(w != -1){
			int u = i + vl[w];
			curr = max(curr, i+1);
			curr = min(curr , MX - 1);
			// if(i < 8){
			// 	cout<<i<<" " <<w <<" " << u <<endl;
			// }
			for(int j = curr; j < min(u , MX) ; j++){
				dp[j] = dp[i] + 1;
			}
			curr = max(curr, u);
			curr = min(curr , MX - 1);
			int wx = adj[w];
			if(u < MX){
				adj[w] = dq[u];
				dq[u] = w;
			}
			w = wx;
		}
	}
	for(int i = 0 ; i < q; i ++){
		int x;
		scanf("%d" , &x);
		int u = dp[x];
		if(u >= 1000000000){
			printf("oo\n");
		}
		else{
			printf("%d\n" , u);
		}
	}
}

Compilation message

brunhilda.cpp: In function 'int32_t main()':
brunhilda.cpp:16: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:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &primes[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~
brunhilda.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &x);
   ~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 117780 KB Output is correct
2 Correct 210 ms 117832 KB Output is correct
3 Correct 206 ms 117880 KB Output is correct
4 Correct 156 ms 117880 KB Output is correct
5 Correct 211 ms 117668 KB Output is correct
6 Correct 155 ms 117664 KB Output is correct
7 Correct 202 ms 117968 KB Output is correct
8 Correct 217 ms 117752 KB Output is correct
9 Correct 259 ms 117788 KB Output is correct
10 Correct 274 ms 117828 KB Output is correct
11 Correct 248 ms 117752 KB Output is correct
12 Correct 151 ms 117752 KB Output is correct
13 Correct 318 ms 117680 KB Output is correct
14 Correct 342 ms 117868 KB Output is correct
15 Correct 225 ms 117780 KB Output is correct
16 Correct 216 ms 117888 KB Output is correct
17 Correct 205 ms 117780 KB Output is correct
18 Correct 155 ms 117816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 117956 KB Output is correct
2 Correct 209 ms 118392 KB Output is correct
3 Correct 391 ms 118236 KB Output is correct
4 Correct 213 ms 117752 KB Output is correct
5 Correct 310 ms 118184 KB Output is correct
6 Correct 210 ms 117788 KB Output is correct
7 Correct 194 ms 117916 KB Output is correct
8 Correct 199 ms 117672 KB Output is correct
9 Correct 361 ms 118344 KB Output is correct
10 Correct 396 ms 118332 KB Output is correct
11 Correct 369 ms 118044 KB Output is correct
12 Correct 270 ms 117872 KB Output is correct
13 Correct 177 ms 117752 KB Output is correct
14 Correct 220 ms 117812 KB Output is correct
15 Correct 395 ms 118068 KB Output is correct
16 Correct 209 ms 118520 KB Output is correct
17 Correct 315 ms 117880 KB Output is correct
18 Correct 460 ms 118452 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 118176 KB Output is correct
2 Correct 395 ms 118280 KB Output is correct
3 Correct 458 ms 118308 KB Output is correct
4 Correct 322 ms 118008 KB Output is correct
5 Correct 253 ms 118648 KB Output is correct
6 Correct 359 ms 118104 KB Output is correct
7 Correct 314 ms 118776 KB Output is correct
8 Correct 392 ms 118192 KB Output is correct
9 Correct 372 ms 118264 KB Output is correct
10 Correct 283 ms 117836 KB Output is correct
11 Correct 261 ms 117872 KB Output is correct
12 Correct 392 ms 117880 KB Output is correct
13 Correct 381 ms 118252 KB Output is correct
14 Correct 337 ms 118264 KB Output is correct
15 Correct 362 ms 117956 KB Output is correct
16 Correct 350 ms 117880 KB Output is correct
17 Correct 327 ms 118272 KB Output is correct
18 Correct 408 ms 118176 KB Output is correct
19 Correct 202 ms 117872 KB Output is correct
20 Correct 405 ms 118252 KB Output is correct
21 Correct 319 ms 118336 KB Output is correct
22 Correct 457 ms 118732 KB Output is correct
23 Correct 247 ms 118264 KB Output is correct
24 Correct 214 ms 118136 KB Output is correct
25 Correct 318 ms 118036 KB Output is correct
26 Correct 331 ms 118068 KB Output is correct
27 Correct 447 ms 118564 KB Output is correct
28 Correct 217 ms 118136 KB Output is correct
29 Correct 382 ms 118696 KB Output is correct
30 Correct 349 ms 118520 KB Output is correct
31 Correct 246 ms 117944 KB Output is correct
32 Correct 263 ms 118068 KB Output is correct
33 Correct 200 ms 118008 KB Output is correct
34 Correct 345 ms 118648 KB Output is correct
35 Correct 223 ms 118116 KB Output is correct
36 Correct 438 ms 118672 KB Output is correct
37 Correct 251 ms 118684 KB Output is correct
38 Correct 356 ms 118092 KB Output is correct
39 Correct 227 ms 117980 KB Output is correct
40 Correct 338 ms 118108 KB Output is correct
41 Correct 317 ms 118648 KB Output is correct
42 Correct 345 ms 118264 KB Output is correct