Submission #986402

#	Time	Username	Problem	Language	Result	Execution time	Memory
986402		Pyqe	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	215 ms	88744 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

long long n,a[200069],pst[200069],c=0,z=0,fw[200069],fwp;
unordered_map<long long,long long> fq;
unordered_map<long long,queue<long long>> q;

long long count_swaps(vector<int> v)
{
	long long i,k;
	
	n=v.size();
	for(i=1;i<=n;i++)
	{
		if(fq[-v[i-1]])
		{
			a[i]=q[-v[i-1]].front()*2;
			q[-v[i-1]].pop();
			fq[-v[i-1]]--;
		}
		else
		{
			c++;
			a[i]=c*2;
			q[v[i-1]].push(c);
			fq[v[i-1]]++;
		}
		if(v[i-1]<0)
		{
			a[i]--;
		}
	}
	for(i=1;i<=n;i++)
	{
		pst[a[i]]=i;
	}
	for(i=1;i<=n;i++)
	{
		k=0;
		for(fwp=pst[i]-1;fwp>0;fwp-=fwp&-fwp)
		{
			k+=fw[fwp];
		}
		z+=pst[i]-1-k;
		for(fwp=pst[i];fwp<=200000;fwp+=fwp&-fwp)
		{
			fw[fwp]++;
		}
	}
	return z;
}

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