Submission #891451

#	Time	Username	Problem	Language	Result	Execution time	Memory
891451		Faisal_Saqib	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	247 ms	23336 KiB

shoes

#include <vector>
#include <set>
#include <iostream>
#include <map>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
const int N=200010;
vector<int> ind[N];
int pon[N];
bool paired[N];
long long count_swaps(std::vector<int> s)
{
	int n=s.size();
	// set<int> sps;
	// for(auto i:s)
	// 	sps.insert(i);
	// if(n<=(16) or sps.size()<=4)
	// {
	// 	vector<int> sp;
	// 	for(int j=0;j<n;j++)
	// 		ind[s[j]+(n/2)].push_back(j);
	// 	for(auto i:s)
	// 		if(i<0)
	// 			sp.push_back(i);
	// 	long long ans=1e18;
	// 	sort(begin(sp),end(sp));
	// 	int nm=sp.size();
	// 	do{
	// 		for(int j=0;j<=n;j++)
	// 			pon[j]=ind[j].size();
	// 		tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Set;
	// 		long long swaps=0;
	// 		for(int j=nm-1;j>=0;j--)
	// 		{
	// 			int x=-sp[j]+(n/2);
	// 			pon[x]--;
	// 			int indp=ind[x][pon[x]];
	// 			Set.insert(indp);
	// 			swaps+=Set.order_of_key(indp);
	// 			x=sp[j]+(n/2);
	// 			pon[x]--;
	// 			indp=ind[x][pon[x]];
	// 			Set.insert(indp);
	// 			swaps+=Set.order_of_key(indp);
	// 		}
	// 		ans=min(ans,swaps);
	// 	}while(next_permutation(begin(sp),end(sp)));
	// 	return ans;
	// }
	// else
	// {
		tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Set;
		for(int j=0;j<n;j++)
		{
			Set.insert(j);
			s[j]+=(n/2);
			ind[s[j]].push_back(j);
			pon[s[j]]=0;
		}
		// -1,1
		// n,-n
		// 2*n , 0
		long long ans=0;
		for(int i=0;i<n;i++)
		{
			if(!paired[i])
			{
				int to_pair=n-s[i];
				int index1=ind[s[i]][pon[s[i]]];
				pon[s[i]]++;
				int index2=ind[to_pair][pon[to_pair]];
				pon[to_pair]++;
				int heavy_way=Set.order_of_key(index2)-Set.order_of_key(index1+1);
				Set.erase(index2);
				paired[index2]=1;
				ans+=heavy_way+(to_pair<(n/2));
			}
		}
		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