# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
959535 | AndreiBOTO | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
const int NMAX=2e5+5;
queue<int>right_shoe[NMAX];
queue<int>left_shoe[NMAX];
bool viz[NMAX];
int aib[NMAX];
int v[NMAX];
int n;
int lsb(int x)
{
return x&(-x);
}
void update(int p,int val)
{
while(p<=n)
{
aib[p]+=val;
p+=lsb(p);
}
}
long long query(int p)
{
long long s=0;
while(p>0)
{
s+=aib[p];
p-=lsb(p);
}
return s;
}
long long query_range(int x,int y)
{
return query(y)-query(x-1);
}
long long count_swaps(vector<int>a)
{
int i;
long long kon=0;
n=a.size();
for(i=1;i<=n;i++)
v[i]=a[i-1];
for(i=1;i<=n;i++)
{
if(v[i]<0)
left_shoe[-v[i]].push(i);
else
right_shoe[v[i]].push(i);
}
for(i=1;i<=n;i++)
{
if(viz[i])
continue;
if(v[i]<0)
{
int x=left_shoe[-v[i]].front();
int y=right_shoe[-v[i]].front();
kon+=y-x-query_range(x+1,y)-1;
left_shoe[-v[i]].pop();
right_shoe[-v[i]].pop();
update(y,1);
viz[x]=true;
viz[y]=true;
}
else
{
int x=right_shoe[v[i]].front();
int y=left_shoe[v[i]].front();
kon+=y-x-query_range(x+1,y);
left_shoe[v[i]].pop();
right_shoe[v[i]].pop();
update(y,1);
viz[x]=true;
viz[y]=true;
}
}
return kon;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<int>arr={2, 1, -1, -2};
//cout<<count_swaps(arr);
return 0;
}