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<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int MAXN = 200000;
int n, to[MAXN+10];
queue<int> bs[MAXN+10];
long long counter=0;
/*void input()
{
int temp;
cin>>n;
for (int i=0; i<2*n; i++)
{
cin>>temp;
s.push_back(temp);
}
}*/
void output()
{
cout<<counter<<endl;
}
void find_place(vector<int> S)
{
int curr = 0;
int temp;
for (int i=0; i<n; i++)
{
temp = abs(S[i]);
if (S[i]>0)
{
if (!bs[temp].empty() && bs[temp].front()%2==0)
{
//cout<<i<<' '<<bs[temp].front()<<endl;
to[i] = bs[temp].front()+1;
bs[temp].pop();
}
else
{
to[i] = curr+1;
bs[temp].push(curr+1);
curr += 2;
}
}
else
{
if (!bs[temp].empty() && bs[temp].front()%2==1)
{
to[i] = bs[temp].front()-1;
bs[temp].pop();
}
else
{
to[i] = curr;
bs[temp].push(curr);
curr += 2;
}
}
}
}
void sorting()
{
for (int i=0; i<n; i++)
{
int nd=i;
while (to[nd]!=i && nd<n) nd++;
//cout<<i<<" - ";
while (nd!=i)
{
//cout<<nd<<' ';
swap(to[nd], to[nd-1]);
counter++;
nd--;
}
//cout<<endl;
}
}
void solve(vector<int> S)
{
n = S.size();
find_place(S);
sorting();
}
long long count_swaps(vector<int> S)
{
solve(S);
return counter;
}
/*int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
input();
solve();
output();
return 0;
}*/
/*
3
-2 2 2 -2 -2 2
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |