Demo entry 3548944

1517

   

Submitted by anonymous on Jan 20, 2016 at 12:33
Language: C++. Code size: 1.4 kB.

#include <cstdio>
#include <vector>
#include <iostream>

void merge_sort(std::vector<int>& sortableList, int start, int num);
long long int ans = 0;

int main() {
	std::vector<int> sortableList;

	int n = 0;
	std::cin >> n;
	while (n--) {
		int v = 0;
		std::cin >> v;
		sortableList.push_back(v);
	}

	merge_sort(sortableList, 0, sortableList.size());

	printf("%lld", ans);
}

void merge_sort(std::vector<int>& sortableList, int start, int num) {
	if (num == 1) {
		return;
	}
	int mid = num / 2;
	// 두개로 쪼개기

	merge_sort(sortableList, start, mid);
	merge_sort(sortableList, start + mid, num - mid);

	std::vector<int> resultVector;
	int leftBegin = start, rightBegin = start + mid;

	while (
		leftBegin < start + mid &&
		rightBegin < start + num
		)
	{
		if (sortableList[leftBegin] <= sortableList[rightBegin]) {
			resultVector.push_back(sortableList[leftBegin]);
			leftBegin++;
		}
		else {
			resultVector.push_back(sortableList[rightBegin]);
			rightBegin++;
			ans += (start + mid) - leftBegin;
		}
	}


	// 한쪽이 남았을 때
	while (leftBegin < start + mid) {
		resultVector.push_back(sortableList[leftBegin]);
		leftBegin++;
	}

	while (rightBegin < start + num) {
		resultVector.push_back(sortableList[rightBegin]);
		rightBegin++;
	}

	for (int i = 0; i < num; ++i) {
		sortableList[start + i] = resultVector[i];
	}
}

This snippet took 0.02 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).