| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 559343 | LastRonin | 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 "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const ll N = 2e5;
ll n;
vector<ll> st ex[N];
long long count_swaps(vector<int> s) {
n = s.size();
ll pos = 0;
for(auto u : s) {
if(u < 0) {
st.pb(pos++);
}
else {
ex[u].pb(pos++);
}
}
for(int j = 1; j <= n; j++) {
reverse(ex[j].begin(), ex[j].end());
}
ll ans = 0;
for(int j = 0; j < n; j += 2) {
ll z = -1;
for(int i = j; i < n; i++) {
if(s[i] < 0) {
z = i;
break;
}
}
for(int i = z; i > j; i--)
swap(s[i], s[i - 1]), ans++;
z = -1;
for(int i = j + 1; i < n; i++) {
if(s[i] == -s[j]) {
z = i;
}
}
for(int i = z; i > j + 1; i--)
swap(s[i], s[i - 1]), ans++;
}
return ans;
}
