#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct FenwickTree {
vector<int> tree;
FenwickTree(int size) {
tree.resize(size+1, 0);
}
int sum(int pos) {
int ret = 0;
for (int i=pos+1; i>0; i &= (i-1)) ret += tree[i];
return ret;
}
void add(int pos, int val) {
for (int i=pos+1; i<tree.size(); i+=(i & -i)) tree[i] += val;
}
};
ll inversion_cnt(vector<int> arr) {
int n = arr.size();
ll ret = 0;
FenwickTree fen(n);
for (int x: arr) {
ret += fen.sum(n-1) - fen.sum(x);
fen.add(x, 1);
}
sort(arr.begin(), arr.end());
for (int i=0; i<n; ++i) {
if (arr[i] != i) assert(false);
}
return ret;
}
ll count_swaps(vector<int> s) {
int n = s.size() / 2;
vector<vector<int>> arr(n+1);
int num_cnt = n+1;
for (int i=0; i<2*n; ++i) arr[abs(s[i])].push_back(i);
for (int i=1; i<=n; ++i) {
int pos_cnt = 0, neg_cnt = 0;
for (int idx: arr[i]) {
if (s[idx] > 0) {
s[idx] = num_cnt + pos_cnt;
pos_cnt++;
} else {
s[idx] = -(num_cnt + neg_cnt);
neg_cnt++;
}
}
num_cnt += pos_cnt;
assert(pos_cnt == neg_cnt);
}
map<int, int> mp;
for (int i=0; i<s.size(); ++i) {
if (s[i] < 0) {
mp[-s[i]] = mp.size();
}
}
assert(mp.size() == n);
for (int i=0; i<s.size(); ++i) {
assert(mp.find(abs(s[i])) != mp.end());
if (s[i] > 0) {
s[i] = mp[s[i]] * 2 + 1;
} else {
s[i] = mp[-s[i]] * 2;
}
}
return inversion_cnt(s);
}
Compilation message
fish.cpp:1:10: fatal error: shoes.h: No such file or directory
1 | #include "shoes.h"
| ^~~~~~~~~
compilation terminated.
