Submission #198945

#	Time	Username	Problem	Language	Result	Execution time	Memory
198945		kshitij_sodani	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	149 ms	18952 KiB

shoes

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef  long long int llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "shoes.h"

llo tree[200005];
long long n;
llo ss(llo i){
	llo tot=0;
	while(i>0){
		tot+=tree[i];
		i-=(i&-i);
	}
	return tot;
}
void u(llo j){
	while(j<=2*n){
		tree[j]+=1;
		j+=(j&-j);
	}
}
long long count_swaps(vector<int> s){
	n=s.size();
	n/=2;
    memset(tree,0,sizeof(tree));
	vector<llo> aa[n+1];
	vector<llo> bb[n+1];
	for(llo i=0;i<2*n;i++){
		if(s[i]<0){
			aa[-s[i]].pb(i);
		}
		else{
			bb[s[i]].pb(i);
		}
	}
	llo ind[n+1];
	llo ind2[n+1];
	long long tot=0;
	memset(ind,0,sizeof(ind));
	memset(ind2,0,sizeof(ind2));
	llo vis[2*n];
	memset(vis,0,sizeof(vis));
	for(llo i=0;i<2*n;i++){
		//cout<<i<<endl;
		if(vis[i]==1){
		//	cout<<i<<endl;
			continue;
		}
		else{
			if(s[i]<0){
				llo ind3=ind[abs(s[i])];
				llo j=aa[abs(s[i])][ind3];
				llo k=bb[abs(s[i])][ind3];
				llo co=ss(k+1)-ss(j+1);
				tot+=(k-j-1)-co;
				vis[j]=1;
				vis[k]=1;
				u(k+1);
				u(j+1);

			}
			else{
				llo ind3=ind2[abs(s[i])];
				llo j=aa[abs(s[i])][ind3];
				llo k=bb[abs(s[i])][ind3];
				llo co=ss(j+1)-ss(k+1);
			//	cout<<co<<endl;
				tot+=(j-k)-co;
				vis[j]=1;
				vis[k]=1;
				u(j+1);
				u(k+1);
			}
			ind[abs(s[i])]+=1;
			ind2[abs(s[i])]+=1;
	
		}
	}
	return tot;
 
}

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