Submission #143848

#	Time	Username	Problem	Language	Result	Execution time	Memory
143848		Bodo171	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	1078 ms	7420 KiB

shoes

#include "shoes.h"
#include <vector>
#include <iostream>
using namespace std;
const int nmax=200005;
vector<int> v[nmax];
int fin[nmax],po[nmax],a[nmax],b[nmax];
int nr,i,j,mn,col,poz;
long long count_swaps(vector<int> s) {
    int n=s.size();
    n/=2;int ans=0;
    for(int i=0;i<n;i++)
    {
        for(j=1;j<=n;j++)
            a[j]=b[j]=-1;
        for(j=2*i;j<2*n;j++)
        {
            if(s[j]<0&&a[-s[j]]==-1) a[-s[j]]=j;
            if(s[j]>0&&b[s[j]]==-1)   b[s[j]]=j;
        }
        mn=2*n;
        for(j=1;j<=n;j++)
        {
            /*if(a[j]!=-1&&max(a[j]-2*i,0)+max(b[j]-2*i-1,0)<mn)
            {
                mn=max(a[j]-2*i,0)+max(b[j]-2*i-1,0);
                col=j;
            }*/
            if(a[j]!=-1&&a[j]-2*i+b[j]-2*i-1+(a[j]>b[j])<mn)
            {
                mn=a[j]-2*i+b[j]-2*i-1+(a[j]>b[j]);
                col=j;
            }
        }
        j=col;
        for(poz=a[j];poz>2*i;poz--)
            swap(s[poz],s[poz-1]);
        if(a[j]>b[j]) b[j]++;
        for(poz=b[j];poz>2*i+1;poz--)
            swap(s[poz],s[poz-1]);
        ans+=mn;
    }
	return ans;
}

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