Submission #1221559

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

shoes

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

// Fenwick Tree for inversion counting
struct Fenwick {
    int n;
    vector<int> f;
    Fenwick(int _n): n(_n), f(n+1, 0) {}
    void update(int i, int v=1) {
        for (; i <= n; i += i & -i)
            f[i] += v;
    }
    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i)
            s += f[i];
        return s;
    }
};

// Main function
ll count_swaps(vector<int>& S) {
    int N2 = S.size();
    int N = N2 / 2;

    // Gather left and right shoe indices by size
    unordered_map<int, vector<int>> lefts, rights;
    for (int i = 0; i < N2; i++) {
        int x = S[i];
        if (x < 0)
            lefts[-x].push_back(i + 1);
        else
            rights[x].push_back(i + 1);
    }

    // Build target position mapping
    vector<int> P(N2 + 1);
    int pair_idx = 1;
    for (auto& [size, L] : lefts) {
        auto& R = rights[size];
        for (int k = 0; k < (int)L.size(); k++) {
            int li = L[k], ri = R[k];
            P[li] = 2 * pair_idx - 1;
            P[ri] = 2 * pair_idx;
            pair_idx++;
        }
    }

    // Count inversions on P in original order
    Fenwick fenw(N2);
    ll inv = 0;
    for (int i = 1; i <= N2; i++) {
        inv += i - 1 - fenw.query(P[i]);
        fenw.update(P[i], 1);
    }
    return inv;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> S(2*n);
    for (int i = 0; i < 2*n; i++)
        cin >> S[i];

    cout << count_swaps(S) << "\n";
    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccVJMZJq.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccrbXTfj.o:shoes.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccVJMZJq.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