Submission #438728

#	Time	Username	Problem	Language	Result	Execution time	Memory
438728		faruk	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#define ll long long

using namespace std;

class BIT
{
private:
vector<ll> tree;
int n;
public:

BIT(int sizeOfTree)
{
    n = sizeOfTree;
    tree.resize(n + 1, 0);
}

void update(int index, ll value)
{
    index++;
    while (index < n)
        tree[index] += value, index += index & (-index);
}

ll query(int index)
{
    index++;
    ll out = 0;
    while (index > 0)
        out += tree[index], index -= index & (-index);
    return out;
}

};

map<int, vector<int> > located;
map<int, int> used;
map<int, bool> matched;

ll count_swaps(int* S)
{
    int n = sizeof(S);
    BIT passed(n);

    for (int i = 0; i < n; i++)
        located[S[i]].push_back(i);

    ll out = 0;
    for (int i = 0; i < n; i++)
    {
        if (matched[i])
            continue;
        int counterpart = upper_bound(located[-S[i]].begin(), located[-S[i]].end(), used[-S[i]]) - located[-S[i]].begin();
        int val = located[-S[i]][counterpart];
        matched[val] = true;
        int swaps = (val - i) /*+ passed.query(val)*/;
        passed.update(val, 1);
        used[-S[i]] = val;
        used[S[i]] = i;

        if (S[i] < 0)
            swaps--;
        out += swaps;
    }
    return out;
}

Compilation message (stderr)

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