글 읽기 - 머지소트 시간초과

yepp0112 3년 전 0

머지소트로 해결하려고 했으나 계속 시간초과납니다ㅠㅠ

제코드에서 시간을 줄일수있는 방법이 있을까요..??

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int arr[500001];

int c=0;

void mergesort(int arr[],int start,int end){
	int arr2[500001];
	int index=1;
	int mid=(start+end)/2;
	
	int start1=start;
	int end1=mid;
	
	int start2=mid+1;
	int end2=end;
	
	while(start1<=end1 && start2<=end2){
		if(arr[start1]<=arr[start2]){
			arr2[index++]=arr[start1++];
			continue;
		}
		
		else{
			arr2[index++]=arr[start2++];
			c=c+end1-start1+1;
			continue;
		}
	}
	
	while(start1<=end1){
		arr2[index++]=arr[start1++];
	}
	
	while(start2<=end2){
		arr2[index++]=arr[start2++];
	}
	
	int i;
	
	for(i=1;i<=end;i++){
		arr[i]=arr2[i];
	}
}

void sort1(int arr[],int start,int end){
	if(start==end) return;
	int mid=(start+end)/2;
	
	sort1(arr,start,mid);
	sort1(arr,mid+1,end);
	
	mergesort(arr,start,end);
}

int main (){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	
	cin>>n;
	
	int i;
	
	for(i=1;i<=n;i++){
		cin>>arr[i];
	}
	
	sort1(arr,1,n);
	
	cout<<c;
	return 0;
}

yepp0112 3년 전 0

하.. 코드 처음부터 다시 짜니 되네요..

제 코드 읽어주신 모든 분들 감사합니다.

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

문제

문제

출처

ICPC

머지소트 시간초과

yepp0112 3년 전 0

yepp0112 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말