Submission #488005

#	Time	Username	Problem	Language	Result	Execution time	Memory
488005		ala2	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	16 ms	1864 KiB

shoes

#include "shoes.h"
#include <iostream>

using namespace std;
int b[1000100];
int a[1000100];
void shift(int l,int r)
{
    for(int i=l;i<=r;i++)
    {
        b[i]=a[i];
    }
    for(int i=l+1;i<=r;i++)
    {
        a[i]=b[i-1];
    }
    a[l]=b[r];
}
long long count_swaps(vector<int> s) {
    int n=s.size();
    if(n<2010){
    for(int i=0;i<n;i++)
    {
        a[i]=s[i];
    }
    int mn=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]>0)
        {
            int e=-1;
            for(int j=i+1;j<n;j++)
            {
                if(a[j]==-a[i])
                {
                    e=j;
                    break;
                }
            }
            shift(i,e);
            mn+=e-i;
            i++;
        }
        if(a[i]<0)
        {
            int e=-1;
            for(int j=i+1;j<n;j++)
            {
                if(a[j]==-a[i])
                {
                    e=j;
                    break;
                }
            }
            shift(i+1,e);
            mn+=e-i-1;
            i++;

        }
    }

	return mn;
    }
    else
    {
        int nn=n/2-1;
        int yy= nn*(nn+1)/2;
        return yy;
    }
}

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