# 題目: UVa 11495 - Bubbles and Buckets

# 題目說明

你需要將一串有N個數字的陣列做排序，每次只能將相鄰的倆倆數字互換
求由Marcelo先手，Marcelo與Carlos輪流做一次互換，誰會完成排序?

---

INPUT:
每筆測資先輸入一個整數N
接著輸入N個數字 (此數字限制範圍為1 ~ N)

---

OUTPUT:
輸出Marcelo與Carlos中誰會勝出 (完成排序)

# 解題方法

讀入資料後，利用merge sort將資料做排序

ans的方法數為每次選擇右半邊的陣列時，左半邊剩餘的元素數的總和

# 參考程式碼

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int ans;

// merge sort
void merge(vector<int>& P, int front, int mid, int end)
{
	vector<int> left(P.begin() + front, P.begin() + mid + 1);
	vector<int> right(P.begin() + mid + 1, P.begin() + end + 1);
	
	left.emplace_back(INT_MAX);
	right.emplace_back(INT_MAX);

	int l = 0, r = 0;
	for (int i = front; i <= end; ++i)
	{
		if (left[l] <= right[r]) P[i] = left[l++];
		else
		{
			P[i] = right[r++];
			ans += left.size() - l - 1;
		}
	}
}

// merge function
void mergesort(vector<int>& P, int front, int end)
{
	if (front < end)
	{
		int mid = (front + end) / 2;
		mergesort(P, front, mid);
		mergesort(P, mid + 1, end);
		merge(P, front, mid, end);
	}
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int N;
	vector<int> P;

	while (cin >> N, N)
	{
		P.assign(N + 1, 0);
		for (int i = 0; i < N; ++i) cin >> P[i];

		ans = 0;
		mergesort(P, 0, N - 1);

		cout << (ans % 2 ? "Marcelo\n" : "Carlos\n");
	}

	return 0;
}

# 參考資料

https://blog.csdn.net/mobius_strip/article/details/8217669
https://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html
https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/uva-11495---bubbles-and-buckets