Submission #250074

#	Time	Username	Problem	Language	Result	Execution time	Memory
250074		DavidDamian	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	425 ms	149752 KiB

shoes

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
///Binary Indexed Tree
///Determine the minimum number of swaps to obtain a valid sequence
///Remap the elements and find the number of invertions
///The same problem than trying to sort an array with numbers from 1 to N
ll bit[400005];
ll query(int i)
{
    ll sum=0;
    while(i>0){
        sum+=bit[i];
        i-=i&(-i);
    }
    return sum;
}
ll getSum(int a,int b)
{
    return query(b)-query(a-1);
}
void update(int n,int i,ll v)
{
    while(i<=n){
        bit[i]+=v;
        i+=i&(-i);
    }
}
map<int,queue<int> > pairing;
int link[400005];
ll count_swaps(vector<int> s) {
	int n=s.size();
	for(int i=0;i<n;i++){ //Pair each element with its closest opposite
        if(pairing[ -s[i] ].empty()){
            pairing[ s[i] ].push(i);
        }
        else{
            int id=pairing[ -s[i] ].front(); pairing[ -s[i] ].pop();
            link[id]=i;
            link[i]=id;
        }
	}
	int c=0;
	for(int i=0;i<n;i++){ //Remap the data
        if(link[i]<i) continue;
        if(s[i]<0) s[i]=++c, s[ link[i] ]=++c;
        else s[ link[i] ]=++c, s[i]=++c;
	}
	ll total=0;
	for(int i=0;i<n;i++){ //Find inversions
        total+=getSum(s[i]+1,n+1);
        update(n+1,s[i],1);
	}
	return total;
}

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