#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
uint64_t hash_vec(const vector<int> &inp) {
const uint64_t BASE = 998244353;
uint64_t h = 0;
for (int x : inp) {
h = h * BASE + (uint32_t)x + 1;
}
return h;
}
int n;
struct State {
vector<pair<int, int>> swaps;
vector<int> arr;
int moves;
int p1, p2;
};
bool check_valid(State &state, vector<int> &initial) {
vector<int> arrangement = initial;
for (auto &el : state.swaps) {
swap(arrangement[el.first], arrangement[el.second]);
}
bool valid = true;
for (int i = 0; i < n; i++) {
valid = valid && (abs(arrangement[2*i]) == abs(arrangement[2*i+1])) && (arrangement[2*i] < 0 && arrangement[2*i+1] > 0);
}
return valid;
}
bool check_valid(vector<int> &arrangement) {
bool valid = true;
for (int i = 0; i < n; i++) {
valid = valid && (abs(arrangement[2*i]) == abs(arrangement[2*i+1])) && (arrangement[2*i] < 0 && arrangement[2*i+1] > 0);
}
return valid;
}
ll count_swaps(vector<int> s) {
n = s.size() / 2;
ll minimum = 0;
// if all shoes are same size:
// find how many swaps to make each right shoe occupy an odd position
// this forces each left shoe to occupy an even position
set<int> avail; // available odd positions
set<int> right_shoes;
for (int i = 1; i < 2*n; i+=2) avail.insert(i);
for (int i = 0; i < 2 * n; i++) {
int el = s[i];
if (el < 0) continue;
if (i % 2 == 1) avail.erase(i);
else right_shoes.insert(i);
}
while (!avail.empty()) {
int f1 = *avail.begin(), f2 = *right_shoes.begin();
minimum += abs(f1 - f2);
avail.erase(f1);
right_shoes.erase(f2);
}
return minimum;
}
// left shoe if s[i] < 0
// right shoe if s[i] > 0
// ll count_swaps(vector<int> s) {
// n = s.size() / 2;
// int minimum = 0;
// queue<State> q;
// State best;
// q.push(State{{}, s, 0, -1, -1});
// unordered_set<uint64_t> vis;
// vis.insert(hash_vec(s));
// while (!q.empty()) {
// State cur = q.front();
// q.pop();
// // if (check_valid(cur, s)) {
// if (check_valid(cur.arr)) {
// minimum = cur.moves;
// best = cur;
// break;
// }
// for (int i = 1; i < 2*n; i++) {
// for (int j = i-1; j < i+2 && j < 2*n; j++) {
// if (i == j) continue;
// if (((i == cur.p1) && (j == cur.p2)) || ((j == cur.p1) && (i == cur.p2))) continue;
// // vector<pair<int, int>> swaps = cur.swaps;
// // swaps.push_back({i, j});
// // q.push(State{swaps, cur.moves + 1, i, j});
// vector<int> cs = cur.arr;
// swap(cs[i], cs[j]);
// uint64_t h = hash_vec(cs);
// if (vis.count(h)) continue;
// vis.insert(h);
// q.push(State{{}, cs, cur.moves + 1, i, j});
// }
// }
// }
// // cout << "Fastest fix is " << best.moves << " moves\n";
// // for (auto &el : best.swaps) {
// // cout << "Swapped " << el.first << " and " << el.second << "\n";
// // }
// return minimum;
// // return ll(n) * ll(n - 1) / 2LL;
// }
