Submission #730634

#	Time	Username	Problem	Language	Result	Execution time	Memory
730634		lucri	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	171 ms	138896 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <queue>
std::queue<long long>a[200010];
long long aib[200010],n;
void adauga(long long poz,long long val)
{
    for(;poz<=n;poz+=(poz&(-poz)))
        aib[poz]+=val;
}
long long suma(long long poz)
{
    long long ans=0;
    for(;poz>0;poz-=(poz&(-poz)))
        ans+=aib[poz];
    return ans;
}
long long rezolva(long long ps,long long pd)
{
    ps=suma(ps);
    pd=suma(pd);
    if(ps<pd)
        return ps+pd-1;
    return ps+pd;
}
long long count_swaps(std::vector<int> s)
{
	long long ans=0;
	n=s.size();
	for(long long i=1;i<n;++i)
        adauga(i,1);
    for(long long i=0;i<n;++i)
    {
        if(a[n/2-s[i]].empty())
            a[n/2+s[i]].push(i);
        else
        {
            if(s[i]<0)
                ans+=rezolva(i,a[n/2-s[i]].front());
            else
                ans+=rezolva(a[n/2-s[i]].front(),i);
            adauga(i+1,-1);
            adauga(a[n/2-s[i]].front()+1,-1);
            a[n/2-s[i]].pop();
        }
    }
    return ans;
}

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