oj.uz

답안 #26998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
26998 2017-07-08T10:18:46 Z noobprogrammer Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 219 ms 119596 KB 
#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:19:34: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("in.txt" , "r" , stdin) ;
                                  ^
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
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 179 ms 119596 KB Output isn't correct
2 Incorrect 189 ms 119596 KB Output isn't correct
3 Incorrect 183 ms 119596 KB Output isn't correct
4 Incorrect 179 ms 119596 KB Output isn't correct
5 Incorrect 199 ms 119596 KB Output isn't correct
6 Incorrect 186 ms 119596 KB Output isn't correct
7 Incorrect 186 ms 119596 KB Output isn't correct
8 Incorrect 206 ms 119596 KB Output isn't correct
9 Incorrect 183 ms 119596 KB Output isn't correct
10 Incorrect 199 ms 119596 KB Output isn't correct
11 Incorrect 186 ms 119596 KB Output isn't correct
12 Incorrect 203 ms 119596 KB Output isn't correct
13 Incorrect 176 ms 119596 KB Output isn't correct
14 Incorrect 183 ms 119596 KB Output isn't correct
15 Incorrect 179 ms 119596 KB Output isn't correct
16 Incorrect 169 ms 119596 KB Output isn't correct
17 Incorrect 183 ms 119596 KB Output isn't correct
18 Incorrect 166 ms 119596 KB Output isn't correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 186 ms 119596 KB Output isn't correct
2 Incorrect 173 ms 119596 KB Output isn't correct
3 Incorrect 186 ms 119596 KB Output isn't correct
4 Incorrect 183 ms 119596 KB Output isn't correct
5 Incorrect 193 ms 119596 KB Output isn't correct
6 Incorrect 183 ms 119596 KB Output isn't correct
7 Incorrect 173 ms 119596 KB Output isn't correct
8 Incorrect 189 ms 119596 KB Output isn't correct
9 Incorrect 183 ms 119596 KB Output isn't correct
10 Incorrect 176 ms 119596 KB Output isn't correct
11 Incorrect 219 ms 119596 KB Output isn't correct
12 Incorrect 183 ms 119596 KB Output isn't correct
13 Incorrect 209 ms 119596 KB Output isn't correct
14 Incorrect 173 ms 119596 KB Output isn't correct
15 Incorrect 186 ms 119596 KB Output isn't correct
16 Incorrect 189 ms 119596 KB Output isn't correct
17 Incorrect 179 ms 119596 KB Output isn't correct
18 Incorrect 176 ms 119596 KB Output isn't correct

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 206 ms 119596 KB Output isn't correct
2 Incorrect 186 ms 119596 KB Output isn't correct
3 Incorrect 196 ms 119596 KB Output isn't correct
4 Incorrect 173 ms 119596 KB Output isn't correct
5 Incorrect 163 ms 119596 KB Output isn't correct
6 Incorrect 179 ms 119596 KB Output isn't correct
7 Incorrect 176 ms 119596 KB Output isn't correct
8 Incorrect 189 ms 119596 KB Output isn't correct
9 Incorrect 183 ms 119596 KB Output isn't correct
10 Incorrect 193 ms 119596 KB Output isn't correct
11 Incorrect 173 ms 119596 KB Output isn't correct
12 Incorrect 166 ms 119596 KB Output isn't correct
13 Incorrect 169 ms 119596 KB Output isn't correct
14 Incorrect 173 ms 119596 KB Output isn't correct
15 Incorrect 216 ms 119596 KB Output isn't correct
16 Incorrect 186 ms 119596 KB Output isn't correct
17 Incorrect 213 ms 119596 KB Output isn't correct
18 Incorrect 183 ms 119596 KB Output isn't correct
19 Incorrect 189 ms 119596 KB Output isn't correct
20 Incorrect 193 ms 119596 KB Output isn't correct
21 Incorrect 206 ms 119596 KB Output isn't correct
22 Incorrect 189 ms 119596 KB Output isn't correct
23 Incorrect 189 ms 119596 KB Output isn't correct
24 Incorrect 193 ms 119596 KB Output isn't correct
25 Incorrect 166 ms 119596 KB Output isn't correct
26 Incorrect 189 ms 119596 KB Output isn't correct
27 Incorrect 143 ms 119596 KB Output isn't correct
28 Incorrect 166 ms 119596 KB Output isn't correct
29 Incorrect 169 ms 119596 KB Output isn't correct
30 Incorrect 169 ms 119596 KB Output isn't correct
31 Incorrect 163 ms 119596 KB Output isn't correct
32 Incorrect 183 ms 119596 KB Output isn't correct
33 Incorrect 216 ms 119596 KB Output isn't correct
34 Incorrect 189 ms 119596 KB Output isn't correct
35 Incorrect 206 ms 119596 KB Output isn't correct
36 Incorrect 209 ms 119596 KB Output isn't correct
37 Incorrect 196 ms 119596 KB Output isn't correct
38 Incorrect 186 ms 119596 KB Output isn't correct
39 Incorrect 189 ms 119596 KB Output isn't correct
40 Incorrect 193 ms 119596 KB Output isn't correct
41 Incorrect 169 ms 119596 KB Output isn't correct
42 Incorrect 183 ms 119596 KB Output isn't correct