| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1299813 | Agageldi | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include "bits/stdc++.h"
#include "shoes.h"
#include "grader.cpp"
using namespace std;
long long n, ans, fn[500005], vs[500005];
map <long long, set<long long>> vis;
void upd(long long x) {
for(; x <= 2 * n; x += (x & (-x))) {
fn[x]++;
}
return;
}
long long find(long long x) {
long long sum = 0;
for(; x > 0; x -= (x & (-x))) {
sum += fn[x];
}
return sum;
}
long long count_swaps(vector<int> s) {
n = (long long)s.size();
for(long long i = 0; i < n; i++) {
vis[s[i]].insert(i);
}
for(long long i = 0; i < n; i++) {
if(vs[i]) continue;
long long p = *vis[(-1) * s[i]].begin();
long long x1 = find(p) - find(i - 1);
upd(p);
ans += (p - i - 1) - x1;
vs[p] = 1;
vis[-s[i]].erase(p);
vis[s[i]].erase(i);
if(s[i] > 0) ans++;
}
return ans;
}