Submission #211231

#	Time	Username	Problem	Language	Result	Execution time	Memory
211231		eric_xiao	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	115 ms	21240 KiB

shoes

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll BIT[200009];
ll cnt[200009];
vector<ll> A[200009],B[200009];
ll N;
void add(ll p,ll v)
{
    while(p <= N)
    {
        BIT[p] += v;
        p += (p & (-p));
    }
}
ll sum(ll p)
{
    ll ret = 0;
    while(p > 0)
    {
        ret += BIT[p];
        p -= (p & (-p));
    }
    return ret;
}
ll count_swaps(vector<int> S)
{
    ll ans = 0,i;
    N = S.size();
    for(i = 1;i <= N;i++)
    {
        add(i,1);
        if(S[i-1] > 0)
        {
            A[S[i-1]].push_back(i);
        }
        else
        {
            B[-S[i-1]].push_back(i);
        }
    }
    for(i = 1;i <= N;i++)
    {
        ll nw = cnt[abs(S[i-1])];
        if((S[i-1] < 0 && B[abs(S[i-1])][nw] != i) || (S[i-1] > 0 && A[abs(S[i-1])][nw] != i))
        {
            continue;
        }
        cnt[abs(S[i-1])]++;
        ll pr;
        if(S[i-1] < 0)
        {
            pr = A[abs(S[i-1])][nw];
        }
        else
        {
            pr = B[abs(S[i-1])][nw];
            ans++;
        }
        ans += sum(pr)-2;
        add(i,-1);
        add(pr,-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: 15 / 15