#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
ll cntAndMerge(vector<ll>& A, ll l, ll m, ll r) {
ll nLeft = m - l + 1, nRight = r - m;
vector<ll> L(nLeft), R(nRight);
for (ll i = 0; i < nLeft; i++) {
L[i] = A[i + l];
}
for (ll j = 0; j < nRight; j++) {
R[j] = A[m + 1 + j];
}
ll res = 0;
ll i = 0, j = 0, k = l;
while (i < nLeft && j < nRight) {
if (L[i] <= R[j]) {
A[k] = L[i];
k++; i++;
} else {
A[k++] = R[j++];
res += (nLeft - i);
}
}
while (i < nLeft) {
A[k++] = L[i++];
k++; i++;
}
while (j < nRight) {
A[k++] = R[j++];
k++; j++;
}
return res;
}
ll cntInversions(vector<ll>& arr, ll l, ll r) {
ll res = 0;
if (l < r) {
ll m = (r + l) / 2;
res += cntInversions(arr, l, m);
res += cntInversions(arr, m + 1, r);
res += cntAndMerge(arr, l, m, r);
}
return res;
}
ll inversionCount(vector<ll> &arr) {
ll N = arr.size();
return cntInversions(arr, 0, N - 1);
}
ll count_swaps(vector<int> shoes) {
ll N = shoes.size();
ll posPointer = 0, negPointer = 1;
vector<ll> currentShoesRelative;
currentShoesRelative.reserve(N);
for (ll i = 0; i < N; i++) {
if (shoes[i] < 0) {
currentShoesRelative[negPointer] = negPointer;
negPointer += 2;
} else if (shoes[i] > 0) {
currentShoesRelative[posPointer] = posPointer;
posPointer += 2;
}
}
return inversionCount(currentShoesRelative);
}
# | 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... |