# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
296603 | zoooma13 | 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"
#include "shoes.h"
#include "grader.cpp"
using namespace std;
vector <bool> st;
int qry(int l ,int r){
int ret = 0;
for(int i=l; i<=r; i++)
ret += !st[i];
return ret;
}
long long count_swaps(vector<int> s) {
st.resize(s.size());
map <int ,vector<int>> mp;
for(int i=(int)s.size()-1; ~i; i--)
mp[s[i]].push_back(i);
long long ans = 0;
for(int i=0; i<s.size(); i++) if(!st[i]){
int x = s[i]; mp[x].pop_back();
int y_idx = mp[-x].back(); mp[-x].pop_back();
st[i] = 1 ,st[y_idx] = 1;
ans += qry(i+1 ,y_idx-1)+(x > 0);
}
return ans;
}