글 읽기 - 틀린 케이스를 도저히 못찾겠습니다 ㅠㅠ

pwc99 5년 전 0

예외처리도 다 해준 것 같고 결과들도 잘 나옵니다...

왜 틀렸다고 나오는 걸까요??

#include <stdio.h>
#include <stdlib.h>

int a[1000005];
int bound[1000005];

int low_bound(int low, int high, int e)
{
    if (low < 0) return 0;
    if (low>=high )
    {
      if (e <= a[low]) return low;
      return low+1;
    }
    int mid=(low+high)/2;
    if (e > a[mid])
        return low_bound(mid+1,high,e);
    return low_bound(low,mid,e);
}

int main(void){
	int n;
	int i,bnd_idx=1;

	scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&a[i]);
		}
	for(i=0;i<n;i++){
		if(bound[bnd_idx-1] < a[i] ) {	//bigger than the last bnd_idx, insert to the last.
			bound[bnd_idx] = a[i];
			bnd_idx++;
		} else {
			if(bound[low_bound(0,bnd_idx-1,a[i])] != a[i]) {
				if(low_bound(0,bnd_idx-1,a[i]) == bnd_idx-1){
					bound[bnd_idx-1] = a[i];
				}
				else
					bound[low_bound(0,bnd_idx-1,a[i])+1] = a[i];
			}
		}
//		for(int j=1;j<bnd_idx;j++)
//			printf("%d ",bound[j]);
//		printf("_%d_%d\n",bnd_idx,low_bound(0,bnd_idx-1,a[i]));
	}

	printf("%d",bnd_idx-1);

	return 0;
}

djm03178 5년 전 16

여기 랜덤 반례 많이 드립니다.

6
8 5 1 10 5 9 
correct = 3, wrong = 2

7
7 2 9 10 3 8 10 
correct = 4, wrong = 5

7
4 8 3 7 1 2 7 
correct = 3, wrong = 2

8
10 9 9 1 9 8 8 9 
correct = 3, wrong = 2

8
9 4 8 2 1 8 4 5 
correct = 3, wrong = 2

9
7 6 2 1 10 10 7 9 4 
correct = 3, wrong = 2

7
1 1 4 10 2 9 2 
correct = 3, wrong = 4

9
6 4 3 6 3 6 9 7 8 
correct = 4, wrong = 3

9
5 5 5 5 3 10 4 1 8 
correct = 3, wrong = 2

6
6 8 8 5 6 8 
correct = 3, wrong = 2

pwc99 5년 전 3

아...정말 감사합니다!

다시 확인해보겠습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 케이스를 도저히 못찾겠습니다 ㅠㅠ

pwc99 5년 전 0

djm03178 5년 전 16

pwc99 5년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말