글 읽기 - 1%에서 틀렸습니다 라고 나옵니다...

js2002 1년 전 0

LIS를 이분탐색을 통해서 구한 코드인데 어디서 틀린걸까요? 혹시 반례가 있을까요??

#include <iostream>
#include <string.h>
# define MAX 1000000001

int seq[1000001];
int tmpArr[1000001];
int record[1000001];
int LISresult[1000001];

int maxValue_in_record(int size)
{
	int maxValue = 0;
	for(int i=0; i<size; i++) {
		if (maxValue < record[i])
			maxValue = record[i];
	}
	return (maxValue);
}

int insert_index(int tasize, int data) {
	int start = 0;
	int end = tasize-1;
	while (start < end) {
		int mid = (start+end)/2;
		if (tmpArr[mid] == data)
			return (mid);
		else if (data < tmpArr[mid])
			end = mid;
		else
			start = mid+1;
	}
	return (end);
}

int find_LIS_length(int size)
{
	int h = 0;
	while (h < size) {
		int insertIndex = insert_index(size, seq[h]);
		tmpArr[insertIndex] = seq[h];
		record[h] = insertIndex;
		h++;
	}
	return (maxValue_in_record(size));
}

int main() {
	int n;
	std::cin >> n;
	for(int i=0; i<n; i++)
		std::cin >> seq[i];
	
	memset(tmpArr, MAX, sizeof(int)*n+1);
	int maxL = find_LIS_length(n);

	//역 추적 하면서 실제 LIS을 찾아내는 과정	
	int ll = maxL;
	int h = n-1;
	while (h >= 0 && ll >= 0) {
		if (record[h] == ll) {
			LISresult[ll] = seq[h];
			ll--;
		}
		h--;
	}
	
	std::cout << maxL + 1 << std::endl; //LIS의 길이 출력
	for(int i=ll+1; i<=maxL; i++)
		std::cout << LISresult[i] << " ";
	
	
	return (0);
}

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

문제

문제

출처

ICPC

1%에서 틀렸습니다 라고 나옵니다...

js2002 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말