Submission #730631

#	Time	Username	Problem	Language	Result	Execution time	Memory
730631		lucri	Arranging Shoes (IOI19_shoes)	C++17	50 / 100	135 ms	137632 KiB

shoes

#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <queue>
std::queue<int>a[200010];
int aib[200010],n;
void adauga(int poz,int val)
{
    for(;poz<=n;poz+=(poz&(-poz)))
        aib[poz]+=val;
}
int suma(int poz)
{
    int ans=0;
    for(;poz>0;poz-=(poz&(-poz)))
        ans+=aib[poz];
    return ans;
}
int rezolva(int ps,int 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)
{
	int ans=0;
	n=s.size();
	for(int i=1;i<n;++i)
        adauga(i,1);
    for(int 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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 20 / 20
• Subtask 6: 0 / 15