Submission #1184079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184079		I_FloPPed21	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	44 ms	19272 KiB

shoes

#include <iostream>
#include <vector>
using namespace std;
const int N=2e5+5;
int n;
vector<int>stg[N];
vector<int>drp[N];
int aib[N],v[N];
bool used[N];
void update(int poz)
{
    for(int i=poz;i<=n;i+=(i&-i))
        aib[i]++;
}
int query(int poz)
{
    int s=0;
    for(int i=poz;i>0;i-=(i&-i))
    {
        s+=aib[i];
    }
    return s;

}
long long count_swaps(vector<int> s)
{
    n=s.size();
    long long ans=0;
    for(int i=n;i>=1;i--)
    {
        v[i]=s[i-1];
        if(v[i]<0)
        {
            stg[-v[i]].push_back(i);
        }
        else
        {
            drp[v[i]].push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(used[i])
            continue;
        if(v[i]<0)
        {
            int poz=drp[-v[i]].back();
            used[poz]=true;
            drp[-v[i]].pop_back();
            ans+=(poz-i-1)-query(poz)+query(i);
            update(i);
            update(poz);
            stg[-v[i]].pop_back();
        }
        else
        {
            int poz=stg[v[i]].back();
            //cout<<i<<" "<<poz<<" "<<"huh"<<'\n';
            used[poz]=true;
            stg[v[i]].pop_back();
            ans+=(poz-i-1)-query(poz)+query(i);
            update(i);
            update(poz);
            ans++;
            drp[v[i]].pop_back();
        }
        //cout<<i<<" "<<ans<<'\n';
    }
    return ans;

}
/*
int main()
{
    cout<<count_swaps({-2, 2, 2, -2, -2, 2});
    return 0;
}
*/

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