Submission #155776

#	Time	Username	Problem	Language	Result	Execution time	Memory
155776		akobi	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	56 ms	19820 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define N 100005
ll n,fix[N],ans,f[2*N];
pair< vector<ll>,ll > v1[N],v2[N];
void upd(ll u)
{
    u++;
    while (u<=2*n)
    {
        f[u]++;
        u+=(u&(-u));
    }
    return;
}
ll get(ll u,ll v)
{
    v++;
    ll tans=0;
    while (v>0)
    {
        tans+=f[v];
        v-=(v&(-v));
    }
    while (u>0)
    {
        tans-=f[u];
        u-=(u&(-u));
    }
    return tans;
}
ll count_swaps(vector<int> a)
{
    n=a.size()/2;
    for (int i=0; i<2*n; i++)
    {
        if (a[i]<0)
        {
            v1[-a[i]].F.pb(i);
            if ( v2[-a[i]].F.size()-v2[-a[i]].S>0 )
            {
                //cout<<i<<" "<<(v2[-a[i]].F)[ v2[-a[i]].S ]<<endl;
                fix[i]= (v2[-a[i]].F)[ v2[-a[i]].S ];
                fix[ (v2[-a[i]].F)[ v2[-a[i]].S ] ]
                    =(v2[-a[i]].F)[ v2[-a[i]].S ];
                v1[-a[i]].S++;
                v2[-a[i]].S++;
            }
        }
        else
        {
            v2[a[i]].F.pb(i);
            if ( v1[a[i]].F.size()-v1[a[i]].S>0 )
            {
                //cout<<i<<" "<<(v1[a[i]].F)[ v1[a[i]].S ]<<endl;
                fix[i]= (v1[a[i]].F)[ v1[a[i]].S ];
                fix[ (v1[a[i]].F)[ v1[a[i]].S ] ]
                    =(v1[a[i]].F)[ v1[a[i]].S ];
                v2[a[i]].S++;
                v1[a[i]].S++;
            }
        }
    }
    for (int i=0; i<2*n; i++)
    {
        upd(fix[i]);
        if (i==fix[i])
            continue;
        ans+=get(fix[i]+1,i);
        if (a[i]<a[fix[i]])
            ans++;
    }
  	return ans;
    //cout<<ans<<endl;
}

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