Submission #1138842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138842		vusal	Arranging Shoes (IOI19_shoes)	C++20	Compilation error	0 ms	0 KiB

shoes

#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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccaEPGk1.o: in function `main':
grader.cpp:(.text.startup+0x289): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status