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>
using namespace std;
long long count_swaps(vector<int>s){
long long n=s.size()/2,ans=0;
queue<long long>pr[2*n+100];
vector<long long>vec={};
for(int i=-n;i<=n;i++) while(pr[i+n].size()) pr[i+n].pop();
for(int i=0;i<2*n;i++) pr[s[i]+n].push(i);
for(int i=0;i<2*n;i++){
if(!s[i]) continue;
if(s[i]>0) ans++;
vec.push_back(pr[-s[i]+n].front());
s[pr[-s[i]+n].front()]=0;
sort(vec.begin(),vec.end());
reverse(vec.begin(),vec.end());
while(vec.back()<=i) vec.pop_back();
for(auto j:vec) if((j>i)&&(j<pr[-s[i]+n].front())) ans--;
ans+=abs(pr[-s[i]+n].front()-i)-1;
pr[s[i]+n].pop();
pr[-s[i]+n].pop();
if(s[i]==-s[i+1]) i++;
// cerr<<ans<<endl;
}
return ans;
}
# | 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... |