글 읽기 - 시간 초과가 왜나는 걸까요?

kth004 7년 전 0

퀵소트로해서 피봇을 정중앙으로 놓고 k값 부분만 부분적으로 정렬 해주었는데 왜 시간초과가 날까요?

#include<iostream>
#include<cstdio>
#define R 5000001LL
using namespace std;
long long arr[R];
long long n,k;
int swap_arr(long long i,long long j)
{
	long long swap;

	swap=arr[i];
	arr[i]=arr[j];
	arr[j]=swap;

	return 0;
}

long long quick_sort(long long left,long long right,long long result){
	long long pivot;
	long long i,j;
	i=left;
	j=right;
	pivot=(left+right)/2;
	if(left>=right){
		return left;
	}
	while(i<j){

		while(arr[i]<arr[pivot]){
			i++;
		}

		while(arr[j]>arr[pivot]){
			j--;
		}
		if(pivot==j){
			pivot=i;
		}
		else if(pivot==i){
			pivot=j;
		}
		swap_arr(i,j);
	}
	swap_arr(j,pivot);

	if(k==pivot){
		result=pivot;
		return result;
	}
	if(k<pivot){
		result=quick_sort(left,pivot,result);
	}
	else if(k>pivot){
		result=quick_sort(pivot+1,right,result);
	}
	return result;
}
int main(){
	long long i,result,j;
	result=0;
	scanf("%lld%lld",&n,&k);
	k-=1;
	
	for(i=0;i<n;i++){
		scanf("%lld",&arr[i]);
	}

	
	result=quick_sort(0,n-1,0);

	printf("%lld\n",arr[result]);

	return 0;
}

chogahui05 7년 전 0

시간 초과가 나는 예입니다.

2 2 2 2 2 2 2

i와 j가 결코 바뀌지 않지요.

while(arr[i]<arr[pivot])
{
	i++;
}

while(arr[j]>arr[pivot])
{
	j--;
}

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

문제

문제

출처

ICPC

시간 초과가 왜나는 걸까요?

kth004 7년 전 0

chogahui05 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말