Submission #593982

#	Time	Username	Problem	Language	Result	Execution time	Memory
593982		1ne	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	628 ms	149116 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> arr) {
	int n = (int)arr.size();
	map<int,queue<int>>index,index2;
	int time = 1;
	for (int i = 0;i<n;++i){
		if (arr[i] < 0){
			index[-arr[i]].push(i);
		}
		else index2[arr[i]].push(i);
	}
	vector<int>order(n);
	for(int i = 0;i<n;++i){
		if (index[abs(arr[i])].empty())continue;
		if (arr[i] > 0 && index2[arr[i]].front() == i){
			order[index[arr[i]].front()] = time++;
			order[i] = time++;
			index[arr[i]].pop();
			index2[arr[i]].pop();
		}
		else if (arr[i] < 0 && index[-arr[i]].front() == i){
			order[i] = time++;
			order[index2[-arr[i]].front()] = time++;
			index[-arr[i]].pop();
			index2[-arr[i]].pop();
		}
	}
	function<long long(int,int,int)>merge = [&](int left,int mid,int right){
		int i = left,j = mid + 1;
		long long ans = 0;
		vector<int>temp(right - left + 1);
		int cur = 0;
		while(i<=mid && j<=right){
			if (order[i] > order[j]){
				ans+=mid - i + 1;
				temp[cur++] = order[j++];
			}
			else{
				temp[cur++] = order[i++];
			}
		}
		while(i<=mid){
			temp[cur++] = order[i++];
		}
		while(j<=right){
			temp[cur++] = order[j++];
		}
		int p = 0;
		while(left<=right){
			order[left++] = temp[p++];
		}
		return ans;
	};
	function<long long(int,int)>merge_sort =[&](int left,int right){
		if (left>=right)return 0LL;
		int mid = (left + right)>>1;
		long long ans = 0;
		ans+=merge_sort(left,mid);
		ans+=merge_sort(mid + 1,right);
		ans+=merge(left,mid,right);
		return ans;
	};
	return merge_sort(0,n - 1);
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15