Submission #239039

#	Time	Username	Problem	Language	Result	Execution time	Memory
239039		T0p_	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	115 ms	16760 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define N 200005

int p[N], arr[N], tmp[N];
bool visit[N];
vector<int> idx[N];

int sgn(int n)
{
	return (n < 0) ? -1 : 1;
}

long long inv(int l, int r)
{
	if(l == r) return 0;
	int mid = (l+r)>>1;
	long long ret = inv(l, mid) + inv(mid+1, r);
	int i = l, j = mid+1, k = l;
	while(i <= mid && j <= r)
	{
		if(arr[i] < arr[j]) tmp[k++] = arr[i++];
		else
		{
			ret += mid-i+1;
			tmp[k++] = arr[j++];
		}
	}
	while(i <= mid) tmp[k++] = arr[i++];
	while(j <= r) tmp[k++] = arr[j++];
	for(int i=l ; i<=r ; i++) arr[i] = tmp[i];
	return ret;
}

long long count_swaps(vector<int> s)
{
	int n = s.size(), now = 1;
	for(int i=0 ; i<n ; i++) idx[s[i]+100000].push_back(i);
	for(int i=0 ; i<n ; i++) 
	{
		if(visit[i]) continue ;
		arr[i] = now * sgn(s[i]);
		arr[idx[100000-s[i]][p[100000-s[i]]]] = -arr[i];
		visit[i] = true;
		visit[idx[100000-s[i]][p[100000-s[i]]]] = true;
		p[100000+s[i]]++;
		p[100000-s[i]]++;
		now++;
	}
	for(int i=0 ; i<n ; i++)
	{
		int d = 2 * abs(arr[i]);
		if(arr[i] > 0) d++;
		arr[i] = d;
	}
	return inv(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