Submission #26999

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
26999	2017-07-08T10:19:57 Z	noobprogrammer	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	5.55556 / 100	1000 ms	119596 KB

brunhilda

#include <bits/stdc++.h>
using namespace std ;

int n , m , pr[100010] , mx[10000010] , ft[10000010] , ptr , dp[10000010] ;
const int N = 1e7 ; 
// 1e7 - x + 1 ;

void upd(int x , int val){
	for( ;x<=N ;x+= (x&(-x))) ft[x] = min(ft[x] , val) ;
}

int qr(int x){
	int res = 1e9 ; 
	for(;x>0;x-=(x&(-x)) ) res = min(ft[x] , res) ;
	return res ;
}

int main(){
	// freopen("in.txt" , "r" , stdin) ;
	// freopen("out.txt" , "w" , stdout) ;
	scanf("%d%d" , &n,&m ) ;
	for(int i = 1 ;i<=N;i++) ft[i] = 1e9 ; 
	for(int i=0;i<n;i++) {
		scanf("%d" , pr+i) ;
		for(int j=0 ; j <= (int)1e7 ; j+=pr[i]) mx[j] = max(mx[j] , pr[i]) ;
	}
	upd( 1e7 - mx[0] + 2 , 1 ) ;
	int val ;
	for(int i=1;i<=N;i++){
		ptr = N-i+1 ;
		dp[i] = qr(ptr) ;
		// printf("%d %d %d\n" , i , dp[i] , ptr) ;
		ptr = N - (i + mx[i] - 1 ) + 1 ; 
		if(dp[i] == 1e9) continue ;
		if(ptr > N) continue ;
		upd(ptr , dp[i] + 1) ;
	}
	for(int i=0;i<m;i++){
		scanf("%d" , &val) ;
		if(dp[val] == 1e9) printf("oo\n") ;
		else printf("%d\n" , dp[val] ) ;
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:21:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d" , &n,&m ) ;
                         ^
brunhilda.cpp:24:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , pr+i) ;
                      ^
brunhilda.cpp:39:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &val) ;
                      ^

Subtask #1
5.55555555556 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	219 ms	119596 KB	Output is correct
2	Execution timed out	1000 ms	119596 KB	Execution timed out
3	Correct	219 ms	119596 KB	Output is correct
4	Execution timed out	1000 ms	119596 KB	Execution timed out
5	Execution timed out	1000 ms	119596 KB	Execution timed out
6	Correct	223 ms	119596 KB	Output is correct
7	Correct	219 ms	119596 KB	Output is correct
8	Correct	283 ms	119596 KB	Output is correct
9	Execution timed out	1000 ms	119596 KB	Execution timed out
10	Execution timed out	1000 ms	119596 KB	Execution timed out
11	Execution timed out	1000 ms	119596 KB	Execution timed out
12	Execution timed out	1000 ms	119596 KB	Execution timed out
13	Execution timed out	1000 ms	119596 KB	Execution timed out
14	Execution timed out	1000 ms	119596 KB	Execution timed out
15	Execution timed out	1000 ms	119596 KB	Execution timed out
16	Execution timed out	1000 ms	119596 KB	Execution timed out
17	Execution timed out	1000 ms	119596 KB	Execution timed out
18	Execution timed out	1000 ms	119596 KB	Execution timed out

Subtask #2
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	119596 KB	Execution timed out
2	Execution timed out	1000 ms	119596 KB	Execution timed out
3	Execution timed out	1000 ms	119596 KB	Execution timed out
4	Execution timed out	1000 ms	119596 KB	Execution timed out
5	Execution timed out	1000 ms	119596 KB	Execution timed out
6	Execution timed out	1000 ms	119596 KB	Execution timed out
7	Execution timed out	1000 ms	119596 KB	Execution timed out
8	Execution timed out	1000 ms	119596 KB	Execution timed out
9	Execution timed out	1000 ms	119596 KB	Execution timed out
10	Execution timed out	1000 ms	119596 KB	Execution timed out
11	Execution timed out	1000 ms	119596 KB	Execution timed out
12	Execution timed out	1000 ms	119596 KB	Execution timed out
13	Execution timed out	1000 ms	119596 KB	Execution timed out
14	Execution timed out	1000 ms	119596 KB	Execution timed out
15	Execution timed out	1000 ms	119596 KB	Execution timed out
16	Execution timed out	1000 ms	119596 KB	Execution timed out
17	Execution timed out	1000 ms	119596 KB	Execution timed out
18	Execution timed out	1000 ms	119596 KB	Execution timed out

Subtask #3
0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1000 ms	119596 KB	Execution timed out
2	Execution timed out	1000 ms	119596 KB	Execution timed out
3	Execution timed out	1000 ms	119596 KB	Execution timed out
4	Execution timed out	1000 ms	119596 KB	Execution timed out
5	Execution timed out	1000 ms	119596 KB	Execution timed out
6	Execution timed out	1000 ms	119596 KB	Execution timed out
7	Execution timed out	1000 ms	119596 KB	Execution timed out
8	Execution timed out	1000 ms	119596 KB	Execution timed out
9	Execution timed out	1000 ms	119596 KB	Execution timed out
10	Execution timed out	1000 ms	119596 KB	Execution timed out
11	Execution timed out	1000 ms	119596 KB	Execution timed out
12	Execution timed out	1000 ms	119596 KB	Execution timed out
13	Execution timed out	1000 ms	119596 KB	Execution timed out
14	Execution timed out	1000 ms	119596 KB	Execution timed out
15	Execution timed out	1000 ms	119596 KB	Execution timed out
16	Execution timed out	1000 ms	119596 KB	Execution timed out
17	Execution timed out	1000 ms	119596 KB	Execution timed out
18	Execution timed out	1000 ms	119596 KB	Execution timed out
19	Execution timed out	1000 ms	119596 KB	Execution timed out
20	Execution timed out	1000 ms	119596 KB	Execution timed out
21	Execution timed out	1000 ms	119596 KB	Execution timed out
22	Execution timed out	1000 ms	119596 KB	Execution timed out
23	Execution timed out	1000 ms	119596 KB	Execution timed out
24	Execution timed out	1000 ms	119596 KB	Execution timed out
25	Execution timed out	1000 ms	119596 KB	Execution timed out
26	Execution timed out	1000 ms	119596 KB	Execution timed out
27	Execution timed out	1000 ms	119596 KB	Execution timed out
28	Execution timed out	1000 ms	119596 KB	Execution timed out
29	Execution timed out	1000 ms	119596 KB	Execution timed out
30	Execution timed out	1000 ms	119596 KB	Execution timed out
31	Execution timed out	1000 ms	119596 KB	Execution timed out
32	Execution timed out	1000 ms	119596 KB	Execution timed out
33	Execution timed out	1000 ms	119596 KB	Execution timed out
34	Execution timed out	1000 ms	119596 KB	Execution timed out
35	Execution timed out	1000 ms	119596 KB	Execution timed out
36	Execution timed out	1000 ms	119596 KB	Execution timed out
37	Execution timed out	1000 ms	119596 KB	Execution timed out
38	Execution timed out	1000 ms	119596 KB	Execution timed out
39	Execution timed out	1000 ms	119596 KB	Execution timed out
40	Execution timed out	1000 ms	119596 KB	Execution timed out
41	Execution timed out	1000 ms	119596 KB	Execution timed out
42	Execution timed out	1000 ms	119596 KB	Execution timed out

Submission #26999

Compilation message

Subtask #1 5.55555555556 / 20.0

Subtask #2 0 / 20.0

Subtask #3 0 / 60.0

Subtask #1
5.55555555556 / 20.0

Subtask #2
0 / 20.0

Subtask #3
0 / 60.0