Submission #1064024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064024		TlenekWodoru	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	70 ms	15712 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
int miejsce[100009][2];
vector<int>V1[100009],V2[100009];
int Tre[1000000];
int base;
void Przedzial(int l, int p, int dod)
{
    l+=base;
    p+=base;
    while(l<=p)
    {
        if(l%2==1)
        {
            Tre[l]+=dod;
            l++;
        }
        if(p%2==0)
        {
            Tre[p]+=dod;
            p--;
        }
        l>>=1;
        p>>=1;
    }
}
int Punkt(int v)
{
    v+=base;
    int wynik=0;
    while(v>0)
    {
        wynik+=Tre[v];
        v>>=1;
    }
    return wynik;
}
int TworzenieDrzewa(int x)
{
    int u=1;
    while(x>0)
    {
        x>>=1;
        u<<=1;
    }
    return u;
}
long long count_swaps(vector<int>tab)
{
    long long wynik=0;
    const int n=tab.size();
    const int n2=n/2;
    for(int i=0;i<n;i++)
    {
        if(tab[i]<0)
        {
            V1[-tab[i]].push_back(i);
        }
        else if(tab[i]>0)
        {
            V2[tab[i]].push_back(i);
        }
    }
    for(int i=1;i<=n2;i++)
    {
        reverse(V1[i].begin(),V1[i].end());
        reverse(V2[i].begin(),V2[i].end());
    }
    base=TworzenieDrzewa(n);
    for(int i=0;i<n;i++)
    {
        Tre[i+base]=i;
    }
    for(int i=0;i<n;i++)
    {
        const int u=abs(tab[i]);
        if(tab[i]<0&&(int)V1[u].size()>0&&V1[u].back()==i)
        {
            int u1=Punkt(V1[u].back());
            int u2=Punkt(V2[u].back());
            Przedzial(0,V2[u].back(),1);
            wynik+=u2-u1-1;
        }
        else if(tab[i]>0&&(int)V2[u].size()>0&&V2[u].back()==i)
        {
            int u1=Punkt(V2[u].back());
            int u2=Punkt(V1[u].back());
            Przedzial(0,V1[u].back(),1);
            wynik+=u2-u1;
        }
        else{continue;}
        V1[u].pop_back();
        V2[u].pop_back();
    }
	return wynik;
}

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