| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1184078 | I_FloPPed21 | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#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;
}