Submission #168356

#	Time	Username	Problem	Language	Result	Execution time	Memory
168356		Andrei_Cotor	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	108 ms	21240 KiB

shoes

#include "shoes.h"
//#include<bits/stdc++.h>

using namespace std;

vector<int> St[200005],Dr[200005];
int IndSt[200005],IndDr[200005];
int Viz[200005];
int F[200005];

int query(int poz)
{
    int rez=poz;
    while(poz>0)
    {
        rez+=F[poz];
        poz=poz-(poz&(poz^(poz-1)));
    }
    return rez;
}

void update(int poz, int val)
{
    while(poz<=200000)
    {
        F[poz]+=val;
        poz=poz+(poz&(poz^(poz-1)));
    }
}

long long count_swaps(vector<int> V)
{
    int n=V.size();
    for(int i=0; i<n; i++)
    {
        if(V[i]<0)
            St[-V[i]].push_back(i);
        else
            Dr[V[i]].push_back(i);
    }

    long long rez=0;
    for(int i=0; i<n; i++)
    {
        if(Viz[i])
            continue;
        Viz[i]=1;
        if(V[i]<0)
        {
            IndSt[-V[i]]++;

            int other=Dr[-V[i]][IndDr[-V[i]]];
            Viz[other]=1;
            IndDr[-V[i]]++;

            rez+=1LL*(query(other+1)-query(i+1)-1);
            update(other+1,-1);
            update(i+1+1,1);
        }
        else
        {
            IndDr[V[i]]++;

            int other=St[V[i]][IndSt[V[i]]];
            Viz[other]=1;
            IndSt[V[i]]++;

            rez+=1LL*(query(other+1)-query(i+1));
            update(other+1,-1);
            update(i+1+1,1);
        }
    }
    return rez;
}

/*
int main()
{
    int n;
    cin>>n;
    vector<int> A;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        A.push_back(x);
    }
    cout<<count_swaps(A)<<"\n";
    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