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>
#define ll long long
#pragma GCC optimize ("Ofast","unroll-loops")
using namespace std;
#define all(x) x.begin(),x.end()
#define pb push_back
const ll MAXN = 1e5 + 4 ;
ll BIT[MAXN];
bool vis[MAXN];
vector<ll> adj[MAXN];
ll n ;
void update ( ll idx , ll x)
{
while(idx<=MAXN)
{
BIT[idx]+=x;
idx+=idx&(-idx);
}
}
ll getsum(ll idx)
{
ll sum =0;
while(idx>0)
{
sum+=BIT[idx];
idx-=idx&(-idx);
}
return sum;
}
ll getran(ll a , ll b)
{
if(a)
return getsum(b)-getsum(a-1);
return getsum(b);
}
ll get_id(ll x){
if(x > 0)return x;
else return -x+n;
}
long long count_swaps (vector<int>s)
{
n = s.size()/2;
set<pair<ll,ll>>pq ;
ll ans = 0 ;
for(ll i =0 ;i <s.size();i++)
{
pq.insert({i,s[i]});
if(s[i]>0)adj[s[i]].pb(i);
else
{
adj[get_id(s[i])].pb(i);
}
}
for(auto it : adj)
{
reverse(all(it));
}
while(pq.size())
{
if(vis[pq.begin()->first])
{
pq.erase(pq.begin());
continue;
}
ll cur = -pq.begin()->second;
ll idx = get_id(cur);
ll to = adj[idx].back();
adj[get_id(-cur)].pop_back();
ll dist=(to+getran(to,MAXN-1))-(pq.begin()->first+getran(pq.begin()->first,MAXN-1));
if(pq.begin()->second < 0)dist--;
ans +=dist;
vis[pq.begin()->first]=1;
vis[to]=1;
update(to,1);
}
return ans ;
}
/*
int main ()
{
ios_base::sync_with_stdio(0);
int n; cin >> n;
vector<int> v;
for(int i(0); i < n;i++){
int x; cin >> x;
v.push_back(x);
}
cout << count_swaps(v);
return 0;
}
*/
Compilation message (stderr)
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(ll i =0 ;i <s.size();i++)
~~^~~~~~~~~
# | 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... |