Submission #159186

#	Time	Username	Problem	Language	Result	Execution time	Memory
159186		Mathew	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	40 ms	7160 KiB

shoes

#include<bits/stdc++.h>
using namespace std;

long long n,to[2500],pairs=0,br=0;
queue <long long> found[2500];
long long from[2500],perm[2500];

long long count_swaps(vector <int> shoes)
{
    long long i,j;
    n=shoes.size()/2;
    for(i=0;i<2*n;i++)perm[i]=i;
    for(i=0;i<2*n;i++)
    {
        if(shoes[i]<0)
        {
            if(found[shoes[i]+n].empty()==false)
            {
                to[i]=found[shoes[i]+n].front();
                found[shoes[i]+n].pop();
            }
            else
            {
                to[i]=pairs;
                found[n-shoes[i]].push(pairs+1);
                pairs+=2;
            }
        }
        
        else
        {
            if(found[shoes[i]+n].empty()==false)
            {
                to[i]=found[shoes[i]+n].front();
                found[shoes[i]+n].pop();
            }
            else
            {
                to[i]=pairs+1;
                found[n-shoes[i]].push(pairs);
                pairs+=2;
            }
        }
    }
    
    for(i=0;i<2*n;i++)from[to[i]]=i;
    
    //for(i=0;i<2*n;i++)cout<<to[i]<<' ';cout<<endl;
    //for(i=0;i<2*n;i++)cout<<from[i]<<' ';cout<<endl;
    
    for(i=0;i<2*n;i++)
    {
        for(j=0;j<perm[from[i]];j++)
        {
            perm[j]++;
        }
        br+=abs(i-perm[from[i]]);
    }
    return br/2;
}

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