Submission #1237085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237085		Muhammad_Aneeq	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	187 ms	24880 KiB

shoes

#include "shoes.h"
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>
using namespace std;
int const N=2e5+10;
int fen[N]={};
void add(int i,int val)
{
	while (i<N)
	{
		fen[i]+=val;
		i=(i|(i+1));
	}
}
int get(int i)
{
	int sm=0;
	while (i>=0)
	{
		sm+=fen[i];
		i=(i&(i+1))-1;
	}
	return sm;
}
int sm(int l,int r)
{
	return get(r)-get(l-1);
}
long long count_swaps(vector<int> s) 
{
	int n=s.size()/2;
	map<int,vector<int>>ind;
	bool vis[2*n]={};
	for (int i=0;i<2*n;i++)
		add(i,1);
	for (int i=2*n-1;i>=0;i--)
		ind[s[i]].push_back(i);
	long long ans=0;
	for (int i=0;i<2*n;i++)
	{
		if (vis[i]) continue;
		int z=ind[-s[i]].back();
		ind[-s[i]].pop_back();
		int g=sm(i,z)-2;
		if (s[i]>0)
			g++;
		ans+=g;
		ind[s[i]].pop_back();
		vis[i]=1;
		vis[z]=1;
		add(i,-1);
		add(z,-1);
	}
	return ans;
}

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