| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1268836 | FaresSTH | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
static inline long long floordiv2(long long x){ // floor(x/2) for negative x too
return (x>=0) ? (x/2) : -(( -x + 1 )/2);
}
// Return -1 if impossible (not enough even slots)
ll count_swaps(const vector<int>& a){
int n = (int)a.size();
vector<int> neg;
neg.reserve(n);
for (int i=0;i<n;i++) if (a[i] < 0) neg.push_back(i);
int m = (int)neg.size();
int E = (n + 1) / 2; // number of even indices: 0,2,4,...
if (m > E) return -1; // impossible: not enough even slots
// v_k = neg[k] - 2*k
vector<long long> v(m);
for (int k=0;k<m;k++) v[k] = (long long)neg[k] - 2LL*k;
// median of v (average O(n) with nth_element)
long long M;
if (m == 0) return 0;
nth_element(v.begin(), v.begin()+m/2, v.end());
M = v[m/2];
auto clamp = [&](long long s){
long long lo = 0, hi = (long long)E - m;
if (s < lo) s = lo;
if (s > hi) s = hi;
return s;
};
auto cost = [&](long long s){
long long sum = 0;
for (int k=0;k<m;k++) sum += llabs( (long long)neg[k] - 2LL*(k + s) );
return sum;
};
// 2*s should be near M; check both floor/ceil (and clamped)
long long sA = clamp( floordiv2(M) );
long long sB = clamp( floordiv2(M + 1) );
return min(cost(sA), cost(sB));
}