Submission #488258

#	Time	Username	Problem	Language	Result	Execution time	Memory
488258		ssense	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	127 ms	139028 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define startt ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long  ll;
using namespace std;
#define vint vector<int>
#define all(v) v.begin(), v.end()
#define MOD 1000000007
#define MOD2 998244353
#define MX 1000000000
#define MXL 1000000000000000000
#define PI (ld)2*acos(0.0)
#define pb push_back
#define sc second
#define fr first
//#define int long long
//#define endl '\n'
#define ld long double
#define NO cout << "NO" << endl
#define YES cout << "YES" << endl

queue<int> q1[100005], q2[100005];

int _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid,
		  int right);
 
/* This function sorts the
   input array and returns the
number of inversions in the array */
int mergeSort(int arr[], int array_size)
{
	int temp[array_size];
	return _mergeSort(arr, temp, 0, array_size - 1);
}
 
/* An auxiliary recursive function
  that sorts the input array and
returns the number of inversions in the array. */
int _mergeSort(int arr[], int temp[], int left, int right)
{
	int mid, inv_count = 0;
	if (right > left) {
		/* Divide the array into two parts and
		call _mergeSortAndCountInv()
		for each of the parts */
		mid = (right + left) / 2;
 
		/* Inversion count will be sum of
		inversions in left-part, right-part
		and number of inversions in merging */
		inv_count += _mergeSort(arr, temp, left, mid);
		inv_count += _mergeSort(arr, temp, mid + 1, right);
 
		/*Merge the two parts*/
		inv_count += merge(arr, temp, left, mid + 1, right);
	}
	return inv_count;
}
 
/* This funt merges two sorted arrays
and returns inversion count in the arrays.*/
int merge(int arr[], int temp[], int left, int mid,
		  int right)
{
	int i, j, k;
	int inv_count = 0;
 
	i = left; /* i is index for left subarray*/
	j = mid; /* j is index for right subarray*/
	k = left; /* k is index for resultant merged subarray*/
	while ((i <= mid - 1) && (j <= right)) {
		if (arr[i] <= arr[j]) {
			temp[k++] = arr[i++];
		}
		else {
			temp[k++] = arr[j++];
 
			/* this is tricky -- see above
			explanation/diagram for merge()*/
			inv_count = inv_count + (mid - i);
		}
	}
 
	/* Copy the remaining elements of left subarray
(if there are any) to temp*/
	while (i <= mid - 1)
		temp[k++] = arr[i++];
 
	/* Copy the remaining elements of right subarray
	   (if there are any) to temp*/
	while (j <= right)
		temp[k++] = arr[j++];
 
	/*Copy back the merged elements to original array*/
	for (i = left; i <= right; i++)
		arr[i] = temp[i];
 
	return inv_count;
}

long long count_swaps(vector<int> s)
{
	int n = s.size();
	int cnt = -1;
	for(int i = 0; i < n; i++)
	{
		if(s[i] < 0)
		{
			cnt+=2;
			q1[-s[i]].push(cnt);
			q2[-s[i]].push(cnt);
		}
	}
	for(int i = 0; i < n; i++)
	{
		if(s[i] > 0)
		{
			int prev = s[i];
			s[i] = q2[s[i]].front()+1;
			q2[prev].pop();
		}
		else
		{
			int prev = s[i];
			s[i] = q1[-s[i]].front();
			q1[-prev].pop();
		}
	}
	int k[n];
	for(int i = 0; i < n; i++)
	{
		k[i] = s[i];
	}
	return mergeSort(k, n);
}
/*
int main()
{
	int n;
	cin >> n;
	vint a(2*n);
	for(int i = 0; i < 2*n; i++)
	{
		cin >> a[i];
	}
	cout << count_swaps(a);
}
 */
/*
5
-2 -1 1 2 -1 1 -2 -1 1 2
 */

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