Submission #1307770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307770		lufychop	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	1101 ms	145864 KiB

shoes

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

using namespace std;

long long n;
map<long long,deque<long long>> mp;

long long count_swaps(vector<int> s)
{
    n=s.size();
    long long ans=0;
    long long LL=0,RR=n-1;
    for(int i=0;i<n;i++)
    {
        mp[s[i]].push_back(i);
    }
    while(LL<RR)
    {
        if(s[LL]!=0)
        {
            long long tmp=0;
            long long L=LL+1;
            long long R=mp[-s[LL]].front();
            mp[s[LL]].pop_front();
            mp[-s[LL]].pop_front();
            for(int i=L;i<=R;i++)
            {
                if(s[i]==0)
                {
                    tmp++;
                }
            }
            ans=ans+R-LL-1-tmp;
            // cout<<LL<<R<<"\n";
            if(s[R]<0)
            {
                ans++;
            }
            s[R]=0;
            s[LL]=0;
        }
        if(s[RR]!=0)
        {
            long long tmp=0;
            long long L=mp[-s[RR]].back();
            long long R=RR-1;
            mp[-s[RR]].pop_back();
            mp[s[RR]].pop_back();
            for(int i=L;i<=R;i++)
            {
                if(s[i]==0)
                {
                    tmp++;
                }
            }
            ans=ans+RR-L-1-tmp;
            // cout<<L<<RR<<"\n";
            if(s[L]>0)
            {
                ans++;
            }
            s[L]=0;
            s[RR]=0;
        }
        // cout<<LL<<RR;
        LL++;
        RR--;
    }
	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