Submission #198934

#	Time	Username	Problem	Language	Result	Execution time	Memory
198934		kshitij_sodani	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	6 ms	764 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"
int tree[100005];
long long n;
int ss(int i){
	int tot=0;
	while(i<=2*n){
		tot+=tree[i];
		i+=(i&-i);
	}
	return tot;
}
void u(int j){
	while(j>0){
		tree[j]+=1;
		j-=(j&-j);
	}
}
long long count_swaps(vector<int> s){
	n=s.size();
	n/=2;
    memset(tree,0,sizeof(tree));
	vector<int> aa[n+1];
	vector<int> bb[n+1];
	for(int i=0;i<2*n;i++){
		if(s[i]<0){
			aa[-s[i]].pb(i);
		}
		else{
			bb[s[i]].pb(i);
		}
	}
	int ind[n+1];
	int ind2[n+1];
	long long tot=0;
	memset(ind,0,sizeof(ind));
	memset(ind2,0,sizeof(ind2));
	int vis[2*n];
	memset(vis,0,sizeof(vis));
	for(int i=0;i<2*n;i++){
		//cout<<i<<endl;
		if(vis[i]==1){
			continue;
		}
		else{
			if(s[i]<0){
				int ind3=ind[abs(s[i])];
				int j=aa[abs(s[i])][ind3];
				int k=bb[abs(s[i])][ind3];
				int 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{
				int ind3=ind2[abs(s[i])];
				int j=aa[abs(s[i])][ind3];
				int k=bb[abs(s[i])][ind3];
				int 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: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15