# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1138842 | vusal | Arranging Shoes (IOI19_shoes) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <cmath>
#include <algorithm>
class FenwickTree {
private:
std::vector<int> tree;
int size;
public:
FenwickTree(int n) : tree(n + 1, 0), size(n) {}
void update(int index, int value) {
while (index <= size) {
tree[index] += value;
index += index & (-index);
}
}
int query(int index) {
int sum = 0;
while (index > 0) {
sum += tree[index];
index -= index & (-index);
}
return sum;
}
};
long long count_swaps(std::vector<int>& S) {
int n = S.size();
// Ayaqqabıların ölçülərinə görə yenidən təşkil olunmuş massiv
std::vector<std::pair<int, int>> shoes(n);
for (int i = 0; i < n; ++i) {
shoes[i] = {std::abs(S[i]), S[i] > 0 ? 1 : -1};
}
// Unikal ölçüləri tapmaq
std::vector<int> sizes;
for (auto& shoe : shoes) {
sizes.push_back(shoe.first);
}
std::sort(sizes.begin(), sizes.end());
sizes.erase(std::unique(sizes.begin(), sizes.end()), sizes.end());
// Ölçülərin indekslərini kompressiya etmək
std::unordered_map<int, int> size_to_index;
for (int i = 0; i < sizes.size(); ++i) {
size_to_index[sizes[i]] = i + 1;
}
// Sol və sağ ayaqqabılar üçün ayrı inversiya hesablamaları
std::vector<std::pair<int, int>> left_shoes, right_shoes;
for (int i = 0; i < n; ++i) {
if (shoes[i].second > 0) {
left_shoes.push_back({size_to_index[shoes[i].first], i});
} else {
right_shoes.push_back({size_to_index[shoes[i].first], i});
}
}
// Sol ayaqqabılar üçün inversiya sayını hesablamaq
long long left_inversions = 0;
FenwickTree left_tree(sizes.size());
std::sort(left_shoes.begin(), left_shoes.end());
for (auto& shoe : left_shoes) {
left_inversions += left_tree.query(sizes.size()) - left_tree.query(shoe.first - 1);
left_tree.update(shoe.first, 1);
}
// Sağ ayaqqabılar üçün inversiya sayını hesablamaq
long long right_inversions = 0;
FenwickTree right_tree(sizes.size());
std::sort(right_shoes.begin(), right_shoes.end());
for (auto& shoe : right_shoes) {
right_inversions += right_tree.query(sizes.size()) - right_tree.query(shoe.first - 1);
right_tree.update(shoe.first, 1);
}
return left_inversions + right_inversions;
}