Submission #1347974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1347974		feyza	Arranging Shoes (IOI19_shoes)	C++20	85 / 100	11 ms	1960 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

typedef long long ll;

ll solve1(vector<int> & s)
{
    if(s[0]>0)
        return 1;
    else
        return 0;
}

ll solve8(vector<int> & s)
{
    int sz=s.size();
    ll ans=0;
    for(int i=0;i<sz;i+=2)
    {
        int j=i+1;
        while(j<sz && s[j]!=-s[i])
            j++;

        ans+=(j-(i+1));

        for(int k=j;k>i+1;k--)
            s[k]=s[k-1];
        s[i+1]=-s[i];

        if(s[i]>0)
        {
            swap(s[i],s[i+1]);
            ans++;
        }
    }

    return ans;
}

long long count_swaps(std::vector<int> S)
{
    if(S.size()==2)
        return solve1(S);

    if(S.size()<=2000)
        return solve8(S);

    int cnt_left=0;

    int sz=S.size();
    ll ans=0;
    for(int i=0;i<sz;i++)
    {
        if(S[i]<0)
        {
            cnt_left++;

            ans+=(abs(2*cnt_left-1-(i+1)));
        }
    }

    return ans;
}

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